BOJ 1654 - 랜선 자르기
현재 선의 수 k, 목표로 하는 선의 수 n, 현재 선들의 길이가 주어질 때 선들을 일정 길이로 잘라야 하는데, n보다 크거나 같은 개수를 만들어야 하고, 일정 길이가 최대가 되도록 길이를 정해야 한다.(자르고 남는 나머지 선들은 버린다) 문제 풀이 bin...
Recent posts
DFS의 구현(Recursive/Iterative)
두 구현 방법의 차이 DFS는 자식 노드 중 방문하지 않은 노드가 있으면 현재 노드에서의 탐색을 멈추고 자식 노드로 옮겨가서 DFS를 완료한 후에 다시 돌아오는 구조이다. 이것을 보기 좋게 함수로 구현한 것이 recursive하게 구현하는 방법이고, stack을 이용...
BOJ 11725 - 트리의 부모 찾기
간선 정보와 루트의 번호만 주어질 때 각 노드들의 부모를 출력하는 문제이다. 문제 풀이 루트노드에서부터 자식들을 bfs로 탐색하면서 부모를 찾아내었다. 아래 코드에서 주석들은 풀고나서 다른 사람들의 코드를 보면서 공부한 것으로, 밑에서 설명...
BOJ 9466 - 텀 프로젝트
모든 노드의 out degree가 1인 그래프에서 cycle에 속하지 않은 노드의 개수를 구하는 문제이다. 문제 풀이 component를 생각하여 방문하지 않은 정점마다 dfs를 돌리면서 cycle을 체크하면 된다. cycle체크는 visited벡터를 0/1/-1(...
BOJ 2178 - 미로 탐색
붙어있는 숫자로 입력이 주어진다. 입력을 받고 BFS를 돌리면 된다. 문제 풀이 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...