공부하자

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 그간 일본여행을 다녀오느라 블로그나 공부를 제대로 못했었는데 역시 오랜만에 하니까 기억이 잘 안난다. PS는 그 무엇보다 그냥 매일 꾸준히 하는것이 실력향상을 위한 가장 빠른길인듯 하다. 이 문제는 #2667 단지번호붙이기와 비슷한 유형의 문제다. 이전에 블로그에 올렸던 문제이기도 한데, 1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나 2. 그런 최단 경로의 갯수를 구한다거나 3. 어떤 행렬이나 지..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net BFS를 순회하면서 연결 요소의 갯수가 있는지 찾는 문제다. 처음엔 문제를 잘못 읽고 연결된 그래프가 몇개인지만 세아려서 출력하면 되는줄 알았는데, 아무 간선도 가지지않는 정점도 연결 요소에 포함시켜 구현해야 했다. 방향성 없고 가중치 없는 그래프다 보니 그냥 바로 BFS로 감을 잡고 풀었고, 백준 2606번 바이러스 문제와 유사한 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net BFS 문제를 계속 풀어보고 있는데, 이 문제 또한 비슷한 형태의 알고리즘이다. BFS로 풀리는 문제는 정해진 몇몇개의 특징이 있는 듯 하다. 1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나 2. 그런 최단 경로의 갯수를 구한다거나 3. 어떤 행렬이나 지도를 주고 그 지도에서 같은 부분으로 묶이는 영역을 구한다거나 이런 특정한 조건이 들어간 문제가 있으면 웬만하면 BFS로 접근해라 라는 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net "가장 빠른 시간"을 구해야 하는 문제니 BFS를 적용하여 풀었다. 처음엔 그냥 산술적으로 브루트포스 같은것들을 적용시켜 도전하려 했으나, 주어지는 입력의 최댓값이 100,000이고, 제한시간이 2초니까 O(N^2)짜리 코드로 풀면 시간초과가 날것이다. 따라서, BFS를 이용하여 푸는쪽으로 방향을 잡았다. 그래프를 형태가 인접리스트로 주어지는것이 아니기 때문에 오로지 큐..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net BFS를 활용하면 금방 풀리는 문제이다. 입력으로 주어지는 그래프를 인접 리스트 형식으로 구현해놓고, BFS만 돌리면 끝이다. 다만 여기서 포인트는 BFS를 순회하면서 정점들을 기록하는것이 아닌 정점들의 갯수만 카운트 시키고, 마지막 출력할때에 카운트된 변수에서 1만 빼주면 된다. 문제에서 요구하는 출력 조건이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"이기 때문에 1번 컴퓨터 본인은..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이전에 한번 게시했던 문제인데, 애초에 백준 계정을 새로 파서 푼 흔적이 없어졌기 때문에 한번 더 풀었고, 최근에 DFS랑 BFS 개념을 다시 복습하면서 다시 한번 풀어보았다. 문제 자체에서 어려운점은 크게 없었던 것 같다. 그래프를 인접리스트 형태로 주어지는대로 입력받고 입력받은 그래프를 토대로 각각 DFS와 BFS를 적용하여 풀어내면 되는 문제이다. 필자는..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 요구조건은 꽤 간단하다. 전위순회로 주어진 트리를 후위순회로 변환하면 끝이다. 이때 중요한 키 포인트는 세가지가 있다. 1. 전위순회에서 가장 첫번째 노드는 루트 노드이다. 2. 전위순회에서 루트노드보다 커지는 첫번째 원소를 기점으로 왼쪽, 오른쪽 자식트리가 나뉘게 된다. 3. 나뉜 자식트리에 대하여 1~2의 과정을 재귀 형태로 반복하고, 그 과정에서 맨 첫번째 노드(루트 노드)..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 재귀함수를 활용하여 이진트리의 전위,중위,후위 순회를 출력하는 문제이다. 트리의 입력값도 사전에 다 주고, N의 개수도 최대 26까지이기 때문에 크게 까다로운 점은 없었다. 다만 이 문제에서의 핵심 포인트는 처음 루트값이 A라는 것을 활용하여 다른 자식 노드들을 따로 알파벳으로 접근하지 않고 pair형의 배열의 인덱스로서 접근, 참조하는 것인데, 처음 풀때는 이 부분이 조금 이해가 가질..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 난이도 자체는 단순히 구현만 하면 되는 문제이기에 그리 어려운것은 없었지만, 처음에 문제 접근을 잘못 하면서 시간초과가 났고, 그로 인해 조금 헤맸다. 처음엔 단순히 vector에서 find로 인덱스를 찾고 뭐 그런 방식으로 풀었는데, 제시되는 테스트케이스가 최대 3,000,000이고, find의 시간복잡도가 O(N)이니까, 결국 O(N^2)가 된다. 시간초과가 날수밖에 없는 풀이법인 것이다. 결국 그 방법 말고 비트마스킹을 이용해..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 한동안 서울에 방 잡고 이사한다 뭐다 해서 정신이 없었다. 백준이랑 블로그 글 올리는것도 정말 오랜만인거 같은데, 역시 ps는 꾸준히 풀어보는게 가장 좋다. 몇주 쉬고 이랬더니 감 다 죽었나보다. 이 문제는 map을 이용해서 각 단어가 얼만큼 나왔는지 개수를 세야하는 문제다. map을 이용해 푼다면 쉽게 풀리는 문제였지만, map 구조를 이용하지 않고 풀라고 하면 어떻게 풀어야하지? 모르겠..