겜돌이의 개발일지

문제 백준 20055 컨베이어 벨트 위의 로봇 C++ 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 구현 / 시뮬레이션 문제입니다. 생각보다 코드 구현과정이 어려웠는데, 문제 난이도인 골드 5보다는 어려웠습니다. (골드 4~3급은 된다고 생각) 문제에서 주어진 조건에 따라 1. 벨트가 한 칸 회전한다. 2. 벨트 위의 로봇이 움직일 수 있으면 움직인다. 3. 올리는 칸의 내구도가 0이 아니면 로봇을 올린다. 4. 내구도가 0인 칸이 K개 이상이면 종료한다. 의 4가지 과정을 순서대로..

문제 백준 14890 경사로 C++ 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이해 자체는 어렵지 않은 문제였다. 1. 이차원 배열에 값을 넣어주고 2. 행 / 열을 검사하면서 경사로를 놓을 수 있는지 확인한다. 경사로를 놓을 수 있는지 확인하는 과정은 다음과 같다. 1. 현재 값과 다음 값의 차를 구한다. 2-1) 차가 0인 경우 : 평지이므로 다음 구역으로 넘어간다. 2-2) 차가 1인 경우 : 현재가 더 높다. 따라서 내리막길이 필요하므로 다음 구역부터 그 다음 구역으로 가면서 내리막길을 설치할 수 있는 지 확인한다...

문제 백준 2343 기타 레슨 C++ 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 조건을 보고, 이분 탐색으로 해결할 수 있음을 유추해야 합니다. 순서를 변경하면 안 되고, 모든 동영상을 포함해야 하므로 mid 값에 대해 이분 탐색을 실행합니다. 조건을 만족하면 더 작을 mid 값을, 조건을 만족하지 못한다면 더 큰 mid값을 찾습니다. 길이의 합이 int 범위를 넘어설 수 있으므로 long long으로 선언해주고, mid 값의 최대는 100,000 * 10,000 = 10억이므로 범위에 유의합니다. 58%..

문제 백준 2805 나무 자르기 C++ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 전형적인 이분 탐색 문제입니다. low = 0, high는 나무의 최대 높이로 설정한 뒤, mid 값을 바꿔가며 이분 탐색을 시행합니다. low > high 조건을 만족하기 전의 result 값이 최종결과가 됩니다. sum은 int 범위를 초과할 수 있으므로 long long 타입으로 설정합니다. 한편, N의 최대 개수가 백만이라 시간초과가 나지 않을까 걱정했지만, C++은 N ..

문제 백준 2667 단지번호붙이기 (C++) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 일반적인 BFS / DFS 문제입니다. 이차원배열을 탐색하면서, 방문하지 않았다면 bfs를 시행합니다. 근처에 1인 지역들을 모두 탐색해 cnt로 반환합니다. cnt를 result vector에 넣어주고 정렬합니다. 그 후 result vector의 원소들을 하나씩 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 백준 1260 DFS와 BFS (C++) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 탐색의 가장 기본 of 기본 문제입니다. 주어진 조건에 따라 V부터 DFS 및 BFS를 실행하고, node를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

문제 백준 15654 N과 M (5) C++ 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 n과 m (1)에서 출력값이 1 ~ n 이었다면 n과 m (5)는 사용자 입력을 받아 출력을 해야한다. 알고리즘이 바뀌는 건 없다. 백트래킹을 사용하여 순열을 출력하면 된다. 단 출력 시에는 1 ~ n을 출력하는 것이 아니라 사용자 입력을 받아 오름차순으로 정리한 vector를 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

문제 백준 13335 트럭 C++ 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 트럭이 순차적으로 다리를 건너므로(FIFO) 큐를 이용한다. 3단계로 나눠서 풀면 편하다. 다리 위로 안 올라간 트럭들의 Queue와 다리 위에서 움직이고 있는 트럭 Queue 다리 위에서 움직이고 있는 트럭의 거리를 1증가시켜줄 임시 Queue 3개를 선언한다. 1단계 - 이미 다리 위에 있는 트럭들을 모두 1칸 앞으로 이동시킨다. 1-1 : 이 때 트럭이 다리를 건넜으면, ..

문제 백준 2309 일곱 난쟁이 C++ 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 무난한 브루트 포스 문제이다. 아홉 난쟁이 중에 두 난쟁이는 합에 포함이 안 되고, 100이 되는 경우가 무조건 존재하므로 루프를 돌면서 포함이 안되는 두 난쟁이를 찾고 나머지 난쟁이를 벡터 result에 push해준다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..

문제 백준 1065 한수 C++ 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 N까지 루프를 돌면서 N이 등차수열인지 아닌지 검사합니다. 한 자리, 두 자리 수는 무조건 등차수열이므로 주어진 범위에서는 세 자리 숫자만 검사하면 됩니다. (1000은 한수 아님) 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include using namespace std; int ..