복습 정리 노트

이 포스트에서는 cin 입력 버퍼를 비우고 초기화하는 방법에 대해 다루고 있습니다. 적절한 설명을 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 4458번 : '첫 글자를 대문자로' 문제의 풀이 코드를 함께 활용하도록 하겠습니다. 먼저 중요한 차이부터 설명드리겠습니다. 예를 들어 문자열을 한 줄씩 반복해서 받을 때, 개행 문자 '\n'가 마지막에 남아있기 때문에 이를 비우기 위해서 일반적으로 cin.clear()를 사용해왔는데, clear 함수는 사실은 입력 버퍼를 비우는 것이 아닌, stream을 good state로 돌려주는 함수라고 합니다. 따라서 버퍼를 명확히 비우기 위해서는 ignore 함수를 사용하는 것이 더 정확합니다. 이 때 cin.ignore()로 사용하면 문자 한 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1049번 : '기타줄', 9613번 : 'GCD 합', 21921번 : '블로그' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 무작위로 문제를 뽑아 풀었기 때문에 카테고리는 랜덤입니다. 1049번 : 기타줄 기타 줄을 6개 묶음 또는 낱개로 살 수 있고, 가격이 다른 브랜드가 M가지가 있을 때 N개의 줄을 살 수 있는 최소 가격을 구하는 문제입니다. 이런 그리디 문제의 경우에는 경우를 세워서 어떤 경우 어떤 것이 싼지 체크해보는 것도 좋지만, 빨리 풀고 싶을 때는 그냥 나올 수 있는 경우의 수식들을 모두 세운 뒤 그 중 최솟값을 구하면 됩니다. 가령 이 문제..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 8892번 : '팰린드롬', 9656번 : '돌 게임 2', 1292번 : '쉽게 푸는 문제' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Silver 티어에 해당하며, 랜덤으로 문제를 풀이하고 있기에 알고리즘 분류는 다양하게 나올 수 있습니다. 8892번 : 팰린드롬 주어진 k개의 문자열 중에서 2개를 조합하여 팰린드롬 문자열을 만들 수 있다면 해당 문자열을 출력하고, 그러한 조합이 단 한 가지 경우도 없다면 0을 출력하는 문제입니다. 문제 티어가 Silver V에 해당하고, 알고리즘의 분류가 브루트포스 알고리즘으로 되어있기 때문에 모든 경우의 수를 조합해서 확인해 볼 수 있습니다. #include using na..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2075번 : 'K번째 큰 수', 9658번 : '돌 게임 4', 11004번 : 'K번째 수'의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당합니다. 2075번 : K번째 큰 수 N×N개의 수가 입력될 때 K번째로 큰 수를 출력하는 문제입니다. 문제의 난이도가 Gold 티어이므로 매번 정렬해서 K번째 수를 찾으면 시간 초과가 나도록 설계되어 있을 확률이 높습니다. 따라서 정렬을 사용하기보다는 우선순위 큐를 활용하여 값이 입력될 때마다 N번째 값을 top에 유지시키도록 하여 답을 구해보겠습니다. #include using namespace std; int main(..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14853번 : '동전 던지기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Diamond II에 해당하며, 문제를 풀이하기 위해 조합론에 대한 배경 지식이 필요합니다. 14853번 : 동전 던지기 14853번: 동전 던지기 구사과는 p의 확률로 앞면이 나오고, 1-p의 확률로 뒷면이 나오는 동전을 만드는 기계를 만들었다. 여기서 p는 0과 1사이의 수이다. 하지만, 이 기계에 확률 p를 설정할 수는 없다. 확률 p는 기계가 www.acmicpc.net [0, 1]에서 균등한 확률을 가지는 p와 q가 각각 동전 1과 동전 2를 던졌을 때 앞면이 나오는 확률이라고 했을 때, 동전 1을 n1번 던..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2629번 : '양팔저울', 2293번 : '동전 1', 7579번 : '앱' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP, 동적 계획법의 활용에 대한 이해가 필요합니다. 2629번 : 양팔저울 주어진 질량의 추들을 가지고 구슬의 무게를 확인할 수 있는지를 구하는 문제입니다. 점화식을 구해주면 dp로 쉽게 해결이 가능하므로, 관계식을 찾아봅시다. 예를 들어 a라는 질량을 i-1개의 추들로 측정이 가능했다고 가정해봅시다. 그러면 새로운 b라는 질량의 i번째 추를 가지고 새롭게 측정 가능한 질량은 b, a+b, |a-b|의 3가지입니다. (..

​이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1520번 : '내리막 길', 10942번 : '팰린드롬?' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다. 1520번 : 내리막 길 숫자로 주어진 N×M의 map이 주어지고 (0, 0)에서 더 작은 수로만 이동하여 (N, M)까지 이동한다고 할 때, 몇 가지의 경로가 존재하는지를 찾는 문제입니다. 단순한 DFS로 해결이 가능해보이며, 여기에 DP를 활용하여 경로의 수를 기록하면서 풀이하면 되는 문제입니다. #include #define MAX 500 using namespace std; int..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11066번 : '파일 합치기', 11049번 : '행렬 곱셈 순서' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP(동적 계획법)의 활용에 대한 이해가 필요합니다. 11066번 : 파일 합치기 파일을 합칠 때 인접한 두 덩어리를 합치는 비용은 두 덩어리의 파일 크기의 합일 때, 모든 파일을 하나로 합치도록 하는 최소 비용을 구하는 문제입니다. 당연하겠지만 입력 값들의 크기는 무작위로 주어질 수 있기 때문에 DP를 활용하여 배열에 모든 경우의 수를 기록해나가면서 연산 시간을 감소시키는 방법이 가장 무난한 풀이입니다. 따라서 cost[a][b..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11286번 : '절댓값 힙', 1655번 : '가운데를 말해요' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 각각 Silver I, Gold II 티어에 해당하며, 문제를 풀이하기 위해 우선순위 큐에 대한 이해가 필요합니다. 11286번 : 절댓값 힙 입력된 N에 대해 N개의 입력값이 주어지고, 입력값 x가 0인 경우는 배열에서 절댓값이 가장 작은 값을 (절댓값이 작은 값이 여러 개인 경우 가장 작은 값을) 출력하고, 0이 아닌 경우는 그 값을 배열에 저장하는 쿼리를 수행하는 프로그램을 작성하는 문제입니다. 당연하겠지만 매번 정렬을 하고 원소를 탐색하면 시간 초과가 발생하도록 설계가 되어..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2110번 : '공유기 설치', 1300번 : 'K번째 수' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘에 대한 이해가 필요합니다. 2110번 : 공유기 설치 N개의 집의 좌표가 주어졌을 때, C개의 공유기를 최대한 거리가 서로 멀리 떨어지도록 설치했을 때 공유기 사이의 거리를 구하는 문제입니다. 언뜻 보기에는 고려해야 할 변수가 많기 때문에 공유기 간 최대 거리를 바로 구하는 알고리즘을 찾기 쉽지 않습니다. 그렇기 때문에 이런 경우에는 공유기의 거리 자체를 아무거나 잡고 시작하여 범위 내에서 이..