코후닝

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: 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..

알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 【 풀이 】 각 문자들이 끊기지 않으면서 연속해서 나타나는 경우의 단어의 개수를 세는 문제이다. 우선 각 문자의 등장 여부를 나타내는 알파벳 배열을 선언. 테스트 케이스 내에서 문자열을 입력받은 뒤 문자열의 각 글자를 검사. 이미 글자가 한번 나왔고, 연속되지 않는다면 break. 여기에 해당하지 않는다면, 글자에 해당하는..