코후닝

알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 【 풀이 】 2차원 배열을 순회하면서 '1' 이 나왔을 때 모든 인접 접점을 방문하여 그 개수를 체크하는 문제이다. 즉 DFS, BFS 어느 것을 쓰든 무관하지만 여기선 BFS를 사용했다. 풀이 자체는 간단하다. 2차원 배열을 입력받고, 0부터 [n][n] 까지 순회하면서 '1' 이 적혀 있는 부분부터 그 부..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 【 풀이 】 모든 인접 정점을 방문해야하는 문제라면 DFS와 BFS 둘 다 사용해도 무방하다. 이 문제는 최단 거리를 구해야하기 때문에 BFS 가 적합하다. (모든 가중치가 1이기에, BFS 로 구하면 최단 거리가 된다.) 즉 한칸 움직일 때마다 목적지 까지의 거리가 +1 씩 더해지는 것이다. 【 코드 】 #include #include #define MA..

알고리즘 분류: 수학, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 【 풀이 】 그리디 알고리즘 기초 문제이다. 결국 문제에서 요구하는 것은 6개짜리 패키지의 가격과 낱개의 가격들을 입력받았을 때 어떤 조합으로 사야 최솟값으로 끊어진 기타줄을 바꿀 수 있는지이다. 최솟값을 구할 수 있는 아이디어는 세가지이다. 6개 패키지 중에서 가장 최솟값인 패키지로만 기타줄을 샀을 때(N 초과해도 무관) 낱개 중에서 가장 ..

알고리즘 분류: 수학, 그리디 알고리즘, 정렬 문제 링크: https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 【 풀이 】 A 배열을 정렬하고 B 배열을 정렬하지 않았을 때, 각 요소들을 곱해서 더한 값이 최솟값이 되게 하는 문제이다. 이 문제는 A 배열에서의 최댓값 * B 배열에서의 최솟값을 각각 더해가면 간단하게 해결할 수 있다. 그러나 이 문제는 B 배열을 정렬했다고 해서 큰 문제는 없다. 문제 의도에 맞지 않지만, 그렇다고 해서 더 ..

알고리즘 분류: 구현 문제 링크: https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 【 풀이 】 점수의 개수(n), 태수의 새로운 점수(score), 랭킹 범위(r) 선언 랭크를 저장할 변수(rank_count) 선언 랭킹 리스트 입력 받기 랭킹을 순회한다. -> 기존 점수보다 새로운 점수가 작으면 rank_count +1 점수가 같으면 rank_count 유지 배열 범위에서 벗어나는 점수이면 rank_count = ..

알고리즘 분류: 구현, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 【 풀이 】 입력받을 보드판과 최종 결괏값을 선언한다(string). '.' 이 나올 때까지 순회한다. 한 글자씩 검사해, 글자가 'X'이면 카운트를 센다. '.' 이 나왔을 때 카운트가 홀수이면 반복문을 빠져나와 -1 을 출력한다. '.' 이 나왔을 때 카운트가 짝수이면 결괏값에 '.' 추가 카운트가 2가 되면 결과값에 "BB" 추가 카운트가 4가 되면 결과값에 "AAAA" 추가 최종 결과 출력 【 코드 】 #include #include usin..