개발 블로그

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 이 문제는 풀 수 있는 방법이 매우 많습니다. 백트래킹도 가능하고, 순열로도 풀 수 있습니다. 저는 순열로 풀었는데 C++에 next_permutaion 내장 함수를 이용하면 구현 방식이 간단하고, 무엇보다 가독성이 좋기 때문입니다. 그리고 모든 연산자의 최대 개수가 10! / (3! * 3! * 2! * 2!) = 2520가지입니다. 이러한..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제에서 주어지는 입력은 N(연주할 곡), S(시작 볼륨), M(최대 볼륨)입니다. 두 번째 입력에서는 연주할 곡의 볼륨입니다. 연주는 P-V[i], P+V[i]의 볼륨으로만 연주해야 하고, 구하고자 하는 결과는 마지막 곡을 연주했을 때의 볼륨의 최댓값입니다. D[i][j]는 i번 곡을 j로 연주할 수 있으면 true, 그렇지 않으면 false를 반환합니다. ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 입력은 배낭의 무게(w)와 가치(v)입니다. 배낭의 수용량을 넘지 않으면서 가치의 최댓값을 구하는 문제입니다. 점화식은 다음과 같이 세울 수 있습니다. 물건을 담지 않은 경우 D[i][j] = D[i-1][j] 물건을 담은 경우 D[i][j] = D[i-1][j-w[i]] + v[i] 물건을 담은 경우 에는 수용량과 가치 갱..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제는 파일을 합치는데 최소 비용을 구하는 문제입니다. 테스트케이스를 예시로 들면, C1, C2, C3, C4의 파일 크기는 각각 40 30 30 50입니다. 파일을 합치는 경우의 수는 총 3가지입니다. (C1), (C2, C3, C4) (C1, C2), (C3, C4) (C1, C2, C3), (C4) 1번 경우에는 C2 + C3 = 60, C2 + C3 + C4 = 60 + 50 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제는 기존 팰린드롬(Palindrome)과 유사한 문제입니다. 주어진 수열이 있는데, 시작 인덱스, 끝 인덱스를 입력받고 이 수열이 팰린드롬이면 1을 출력, 그렇지 않으면 0을 출력하는 문제입니다. 팰린드롬은 길이가 1이면 무조건 팰린드롬이고, 2이면 하나만 비교해 주면 됩니다. 이제, 길이가 3인 경우에는 i(첫번째 인덱스), j(마지막 인덱스)에서 인덱스를 하나씩 늘리고(시작 인덱스), 줄여나가면서(마지막 인덱스) 배열 값이 ..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 예전에 풀기도 했었고, 보자마자 DP가 떠올랐습니다. 상담으로 얻을 수 있는 최대 수익을 출력해야 하는데, 이전에 벌어들인 수익을 누적시켜야 하기 때문에 DP를 이용했습니다. 기본 로직은 상담을 하는 것과 하지 않는 것으로 나누고, 상담을 했을 때는 max(상담을 했을 때의 누적값, 그날 상담으로 얻을 수 있는 비용)이고, 상담을 하지 않은 경우에는 max..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이 문제는 오른쪽, 아래쪽, 대각선으로 이동하여 가져올 수 있는 사탕의 개수의 최댓값을 구하는 문제입니다. 다양한 방식으로 풀 수 있는데, 저는 Top-down 방식(재귀)보다 Bottom-Up 방식이 익숙해서 Bottom-up으로 풀었습니다. 기본 로직은 이러합니다. dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 최대힙(priority_queue), 최소힙(priority_queue)를 이용하여 풀 수 있습니다. 힙이 무엇인지 설명드리겠습니다. 힙의 특성에 대해 설명드리겠습니다. 최대힙은 부모 노드는 자식 노드에 들어있는 값보다 커야하고, 최소힙은 부모 노드는 자식 노드에 들어있는 값보다 작아야 합니다. 힙은 완전 이진 트리(Complete Binary Tree)이기 때문에, N..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 DFS, Union Find 등 다양한 알고리즘을 통해 해결할 수 있는 문제입니다. 저는 Union Find로 풀었는데, 이 자료구조를 통해 어떻게 해결했는지 설명드리겠습니다. Union Find란 ? 상호 배타적 집합(Disjoint-set)들의 부분 집합들로 나눠진 원소들에 대한 자료구조 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산(루트를 찾는..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 이 문제는 N명이 한 줄로 서있을 때 서로 마주칠 수 있는 쌍의 수를 구하는 문제입니다. 비교적 어려운 문제는 아니지만, 키가 같은 경우 때문에 고려사항이 많은 문제입니다. 테스트 케이스로 설명 드리겠습니다. case 1 : 7 2 4 1 2 2 5 1 다음과 같이 키가 2 4 1 2 2 5 1 일 경우에는 서로 마주할 수 있는 쌍은 (1 2), (2,3), (2,4), (..