python

문제https://www.acmicpc.net/problem/11967백준 문제집 - 0x09강 - BFS 알고리즘: BFS풀이농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.베시가 불을 켤 수 있는 방의 최대 개수를 구..

문제https://www.acmicpc.net/problem/15655백준 문제집 - 0x0C강 - 백트래킹 알고리즘: 백트래킹풀이N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.- N개의 자연수 중에서 M개를 고른 수열- 고른 수열은 오름차순이어야 한다. 바로 직전의 문제 15645: N과 M (5)과 비슷한 문제다.하지만 이번엔 만들어진 수열 자체가 오름차순이어야 하므로, 현재 숫자보다 작은 숫자들은 수열에 추가될 수 없다.따라서 현재 숫자의 인덱스를 나타낼 변수 start를 함수에 같이 넘겨준다. for문으로 start부터 N까지 순회를 진행하는데,현재 숫자의 다로 다음 인덱스부터 수열에 추가될..

문제https://www.acmicpc.net/problem/15654백준 문제집 - 0x0C강 - 백트래킹 알고리즘: 백트래킹풀이N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수는 모두 다른 수이다. 백트래킹으로 순열(permutation)을 만드는 문제다.순열은 n개의 숫자 중에서 순서를 고려하여 r개를 뽑는 경우의 수를 말한다.permutations 모듈을 사용하면 더 간단하겠지만, '백트래킹' 알고리즘 문제니까 정석대로 풀었다ㅋㅋ 전체 코드# 메모리: 31120KB / 시간: 152msfrom sys import stdininput = stdin.readlineN, M = map(int, input().split()..

문제https://www.acmicpc.net/problem/1074백준 문제집 - 0x0B - 재귀알고리즘: 재귀풀이크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 2의 N제곱만큼의 행렬이 존재할때, N이 1일때부터 N이 될때까지 Z모양으로 탐색한다.다시말해 N = 1일때가 기본값이라는 소리다.2의 1제곱은 2니까 2x2행렬을0 12 3형식으로 방문해야하고, 이 형식을 N까지 확장해나가면 된다. 다만 전체 행렬값을 출력하는게 아닌 r행 c열의 값만 찾으면 되기 때문에, 행렬[r][c]가 포함되는 2x2..

문제https://www.acmicpc.net/problem/1202문제집 - BOJ 길라잡이 베타 (1) 알고리즘: 그리디 Greedy풀이상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.  각 가방이 K개 주어지고, 가방에 따라 담을 수 있는 최대무게값이 다르다.가방 하나당 하나의 보석만 넣을 수 있다.보석은 무게, 가치로 주어진다. 나는 다른 풀이들을 참고하여 3개의 힙을 사용했다.먼저 힙1에는 주어진 보석들을 (무게, 가치)로 저장한다.힙2에는 가방의 무게..

문제https://www.acmicpc.net/problem/9466백준 문제집 - BOJ 길라잡이 베타 (1)알고리즘: DFS풀이주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라. 처음엔 유니온 파인드를 사용해야하나? 싶었고 구상해봤으나 실패...알고보니 DFS(깊이우선탐색) 문제였다. 1번이 2번을 선택하고, 2번이 3번을 선택하고, 3번이 1번을 선택하면 이 셋은 한 팀이다.따라서 이 문제는 그래프에서 사이클의 갯수를 찾는것과 동일하다. 각 번호의 방문여부를 저장할 visited를 생성해주고(편의상 n+1개로)하나씩 순회하며 방문하지 않은 순번일경우 DFS를 실행한다. DFS를 통해 '팀을 가진 사람들'의 수를 구하는것이다. DFS는 실행될때마다..