알고리즘 분류: 구현, 시뮬레이션 문제 링크: https://www.acmicpc.net/problem/10811 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 【 풀이 】 벡터에 1 ~ N 의 숫자를 push_back 하고 start와 end 변수를 받아주고 그 범위를 reverse 함수를 이용해 뒤집어주면 된다. 단 end는 그대로 쓰지만, 0번째 인덱스부터 접근해야 하기 때문에 start는 -1을 한 값을 이용해야 한다. 【 코드 】 #include #include #include using na..
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 문제 링크: 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 = ..