본문 바로가기

분류 전체보기123

[백준 12100] 2048 (Easy) (C++) A. 문제설명 https://www.acmicpc.net/problem/12100 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. 해당 지도 위에서 2048 게임을 수행 3. 기본적인 규칙은 상하좌우로 이동하며 같은 수는 병합되고 해당 이동 위치로 도형들이 달라붙는 것 4. 한번의 이동에서는 한번의 병합만 이루어지며 같은 수의 도형이 3개일 경우 병합의 우선순위는 해당 방향에 가까운 쪽부터 병합 5. 최대 다섯번 이동해서 나올 수 있는 가장 큰 수 구하기 B. 접근법 DFS + 시뮬레이션 먼저 DFS로 상하좌우의 이동 조합을 모두 구하고, 구해진 해당 이동 조합으로 도형 이동 시뮬레이션 수행 C. 풀이 1. 먼저 DFS로 상하좌우의 이동 조합을 모두 구함 2. 구해진 해당 이.. 2020. 6. 2.
[SWEA 9659] 다항식 계산 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXCjsn0KJzcDFAX0 문제에 대한 자세한 설명은 링크 참조 1. 위와 같은 다항식이 존재 2. f0~fN에 대한 정의가 각각 주어지고, 이를 정의하는 ti, ai, bi가 주어질 때 fi(x)를 구할 것 ti =1이면 fi(x) = fai(x) + fbi(x) ti =2이면 fi(x) = ai × fbi(x) ti= 3이면 fi(x)= fai(x) × fbi(x) 3. M개의 수 x1,x2, ⋯, xM이 주어질 때,fN(x1), fN(x2), ⋯, fN(xM)을 계산하라 B. 접근법 다이나믹 프로그래밍 우선 문제에 대한 구현을 시작하기 이전에 해.. 2020. 6. 1.
[SWEA 2383] 점심 식사시간 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. P로 표시된 각 좌표에 사람들이 위치하고, S로 표시된 위치에 계단이 존재 3. 계단에는 한번에 3명의 사람들만 들어갈 수 있고, 계단의 길이는 입력으로 주어지며 그 길이만큼 내려가는 시간이 소요 4. 모든 사람들을 각 계단에 배치하여 내려가게 할 때, 마지막 사람까지 모두 계단을 내려가는 최소의 시간을 구하라 B. 접근법 DFS + 시뮬레이션 우선 계단1/2에 대한 사람들의 선택에 대한 조합을 먼저 DFS로 구한다. 그 후, 각 계단을 선택한 사람.. 2020. 6. 1.
[백준 3190] 뱀 (C++) A. 문제설명 https://www.acmicpc.net/problem/3190 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. 뱀은 (0, 0) 좌표에서 우측으로 이동시작하는데, 아래와 같은 규칙으로 이동 2-1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치 2-2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않음 2-3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줌 3. 수초가 지났을 때 입력으로 들어온 방향전환 명령에 따라 방향을 전환 4. 뱀이 벽이나 자기자신에 부딫히면 종료 5. 마지막으로 종료된 시간 반환 B. 접근법 시뮬레이션 Dummy 게임에 대한 시뮬레이션을 충실히 구현하자. 뱀의 좌표에 .. 2020. 5. 27.
[백준 14499] 주사위 굴리기 (C++) A. 문제설명 https://www.acmicpc.net/problem/14499 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×M인 지도가 존재 2. 지도 위에 주사위의 위치가 주어지고, 주사위는 입력에 따라 동서남북으로 이동 3-1. 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사 3-2. 이동한 칸에 쓰여 있는 수가 0이 아니면, 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 됨 4. 주사위가 이동했을 때 마다 상단에 쓰여 있는 값 출력하기 B. 접근법 시뮬레이션 간단한 시뮬레이션 유형의 문제, 주어진 입력에 따라 주사위를 동서남북으로 굴리는 함수를 따로 구현하였다. 남/북으로 이동시 3/4면이 고정되고 나머지 면이 이동, 동.. 2020. 5. 18.
[백준 16236] 아기 상어 (C++) A. 문제설명 https://www.acmicpc.net/problem/16236 문제에 대한 자세한 설명은 링크 참조 1. N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 존재 2. 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동 3. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있음 4. 먹을 수 있는 물고기가 여러마리라면 거리 -> Y축 좌표 -> X축 좌표 기준으로 우선순위에 따라 선택 5. 물고기 다 먹고 먹을 게 없는 상황에서 걸린 시간 반환 B. 접근법 BFS + 정렬 처음에 시뮬레이션으로 풀어보려다가 실패 후 BFS + 정렬로 다시 풀게 되었다. BFS는 상.. 2020. 5. 15.
[백준 14888] 연산자 끼워넣기 (C++) A. 문제설명 https://www.acmicpc.net/problem/14888 문제에 대한 자세한 설명은 링크 참조 1. N개의 수가 주어지고 그 사이에 N-1개의 연산자를 넣으려고 함 2. N개의 수에 대한 연산자의 조합은 다음과 같이 삽입될 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 3. N-1개의 연산자는 +, -, ×, ÷로 각각 사용할 수 있는 수가 주어짐 4. 연산식 조합 중 최대와 최소를 만드는 것을 구하면 됨 * (중요) 여기서 연산자 우선순위는 무시되고, 연산식은 좌에서 우의 순서로 계산되면 된다. B. 접근법 DFS 주어진 연산자 갯수들을 이용하여 각 연산자들의 배치 조합을 DFS로 모두 만들고, 해당 연산식 중 최대와 최소를 업.. 2020. 5. 8.
[백준 15684] 사다리 조작 (C++) A. 문제설명 https://www.acmicpc.net/problem/15684 문제에 대한 자세한 설명은 링크 참조 1. N개의 세로선과 M개의 가로선이 주어짐 2. 각 세로선에는 H개의 가로선을 놓을 수 있는데, 이는 좌표의 Y축 좌표에 해당된다고 이해하면 된다. 3. 주어진 가로선 이외에 가로선을 전체에서 추가로 3개까지 사용하여, i번째 사다리의 출발점이 i번째 도착점에 도달하도록 사다리를 조작 4. 조작에 추가 가로선이 3개 넘게 필요하다면 -1 반환, 그 이하면 그 갯수 반환 B. 접근법 DFS + 시뮬레이션 1. DFS: 0~3개까지 가로선 놓는 조합 구하기에 사용. 가로선을 추가로 놓는 조합에 대해서는 완전 탐색이 필요하고 해당 조합을 만드는 건 DFS를 사용하자. 2. 시뮬레이션: 가로.. 2020. 5. 8.
[백준 16235] 나무 재테크 (C++) A. 문제설명 https://www.acmicpc.net/problem/16235 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열이 존재, 해당 배열 위에 나무를 키움 2. 매년 봄에는 나무가 각 자리에서 양분먹고 나이 1 증가, 양분이 부족하면 나무는 죽는다.(양분은 나이 적은 순부터 먹음) 3. 여름에는 죽은 나무가 해당 자리에 나이/2 만큼 양분이 됨 4. 가을에는 나무의 위치에서 인접한 8칸이 번식, 이때 5배수의 나이를 가진 나무만 해당함 5. 겨울에는 배열의 각 칸에 양분 추가 6. 최종적으로 K년 뒤의 나무의 총 개수 구하기 B. 접근법 시뮬레이션 문제의 풀이 자체는 어려울 것이 없으나 조건이 이것저것 여러가지 붙어있어 구현할 때 문제를 제대로 이해하지 않으면 실수하기 쉬운 유형이.. 2020. 4. 24.
[백준 14500] 테트로미노 (C++) A. 문제설명 https://www.acmicpc.net/problem/14500 문제에 대한 자세한 설명은 링크 참조 1. N * M 크기의 배열이 존재 2. 배열 위에 5개 종류의 테트리스 도형(테트로미노) 하나를 놓으려고 함 3. 테트로미노는 회전하거나 대칭시킬 수 있다. 4. 각 배열에 엔트리에 숫자 값이 존재하는 데 특정 위치에 이 테트로미노 하나를 놓아 최대의 합을 갖게 하는 경우 출력 B. 접근법 완전탐색과 시뮬레이션 먼저 이 문제에 대해 접근하려면 A. 문제설명의 3번 조건을 고려하여야 한다. 나의 경우 테트로미노의 4방향 회전과 대칭된 도형의 모양을 고려하여 구현하였고, 매 좌표를 탐사할 때 위와 같이 각각의 테트로미노 도형에 대해서 4방향을 회전한 경우의 영역의 엔트리 값의 합을 계산한.. 2020. 4. 12.
[백준 16234] 인구 이동 (C++) A. 문제설명 https://www.acmicpc.net/problem/16234 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열 크기의 각 국가에 국민들 수가 주어짐 2. 각 인접한 칸의 국민 수의 차가 L이상 R이하일 때, 두 나라의 국경선을 염 3. 위 조건에 의해 국경을 열어 연합이 인구이동을 하게 될 때, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 4. 각 국가는 인구이동을 가능한 한 최대한 진행한다. 5. 이때 최대로 이루어질 수 있는 인구이동의 횟수를 반환 B. 접근법 시뮬레이션 문제. 문제상의 조건으로 2000 이상의 이동이 이루어지지 않는 입력만 들어온다고 했으므로, 문제의 내용을 충실하게 구현하여 그대로 적용할 수 있.. 2020. 4. 10.
[백준 15683] 감시 (C++) A. 문제설명 https://www.acmicpc.net/problem/15683 문제에 대한 자세한 설명은 링크 참조 1. N * M 배열 크기의 사무실에 K개의 CCTV가 설치 2. 배열의 각 좌표에는 0: 빈칸, 1~5: CCTV, 6:벽이 주어짐 3. 각 CCTV는 아래와 같이 번호에 따라 감시할 수 있는 방향이 정해져 있다. 4. CCTV는 같은 CCTV를 통과할 수 있으며, 벽은 통과하지 못한다. 5. CCTV는 90도씩 회전이 가능하며 전방향중 가장 감시면적이 넓은 방향을 보게할 때, CCTV가 감시하지 못하는 사각지대 영역의 최소 구하기 B. 접근법 완전탐색과 시뮬레이션 먼저, CCTV의 모든 방향 조합을 구하고, 그 조합에 따라 구해지는 사각지대 영역을 계산하여 그 중 최소를 고르자 C... 2020. 4. 10.
[백준 15686] 치킨 배달 (C++) A. 문제설명 https://www.acmicpc.net/problem/15686 문제에 대한 자세한 설명은 링크 참조 1. N * N 배열 크기의 도시가 존재 2. 배열의 각 좌표에는 0: 빈칸, 1: 집, 2: 치킨집이 존재 3. 각 집에서 가장 가까운 치킨집의 거리를 '치킨거리'라고 하는데, 이는 |r1-r2| + |c1-c2|로 구한다. 4. 여기서, 주어진 치킨집 중 M개의 치킨집만을 남기고 폐업하려고 하는데, 그 조건은 남은 M개의 치킨집이 도시의 모든 집들의 치킨거리가 최소가 되는 경우이다. 5. M개의 치킨집을 살렸을 때 도시의 최소치킨거리를 구할 것 B. 접근법 먼저 이 문제에서 내가 생각한 방식은 DFS이다. M개의 치킨집을 살리는 것에 대한 조합을 DFS로 모두 구해야하고, 그 조합을.. 2020. 3. 28.
[백준 15685] 드래곤 커브 (C++) A. 문제설명 https://www.acmicpc.net/problem/15685 문제에 대한 자세한 설명은 링크 참조 1. 시작점, 방향, 진행세대 수로 정의되는 드래곤 커브가 존재 2. 각 드래곤 커브는 시작점에서 시작해서 출발방향으로 이동하고, 세대의 진행에 따라 이전 세대의 드래곤 커브를 90도 회전시킨 후 끝점에 이어붙여서 확장 3. 주어진 세대로의 확장이 완료된 후 전체 좌표평면 내 드래곤커브가 걸쳐져 있는 사각형의 갯수 계수 이제 이걸 어떻게 그려야하나... 그림을 그려서 풀어야 할까? B. 접근법 처음 이 문제를 받아보고 생각이 든 것은 드래곤 커브 자체의 그림에 대한 생각이었다. 그러나, 이 문제에서 집중해야 할 것은 그림 자체가 아니라 규칙성이다. 각 세대별로 이전 세대의 특징을 가지고.. 2020. 3. 28.
[백준 5373] 큐빙 (C++) A. 문제설명 https://www.acmicpc.net/problem/5373 문제에 대한 자세한 설명은 링크 참조 1. 3 * 3 정육면체의 큐브가 존재 2. 큐브의 각 면에는 위:흰색, 아래:노란색, 앞:빨간색, 뒤:오렌지색, 왼:초록색, 오른:파란색으로 색칠됨 3. 큐브를 돌리는 횟수와 돌리는 면 및 방향(시계/반시계)이 주어짐 4. 주어진 대로 큐브를 모두 돌리고 난 후 윗면 9개 칸의 색상을 출력 문제의 조건은 사실 간단하다. 3 * 3 정육면체 루빅스 큐브를 구현하여 모사하면 되는 것 B. 접근법 큐브를 6개의 3*3 배열로 나누어 좌표에 유의하여 구현한다. 면의 회전방향이 보는 각도에 따라 달라지며 우리가 정의하는 X, Y의 좌표가 뒤집어진 면에서는 그에 맞추어야 하므로 전개도를 그려 헷갈.. 2020. 3. 12.

티스토리툴바