본문 바로가기

알고리즘66

[백준 14501] 퇴사 (C++) A. 문제설명 https://www.acmicpc.net/problem/14501 문제에 대한 자세한 설명은 링크 참조 1. 퇴사전 남은 N일동안 최대한 많은 상담을 하려함 2. 상담시 걸리는 시간 Ti와 받는 보수 Pi가 각각 일별로 주어짐 3. 상담일의 일정을 적절히 배분하여 보수를 최대로 받을 수 있는 금액 구하기 B. 접근법 DFS + 시뮬레이션 N일의 일정동안 상담을 수행할지 말지에 대한 시리얼로 조합을 구하고 해당 조합을 완전탐색으로 시뮬레이션 한다. 그 중 최대가 되는 보수를 구하기 C. 풀이 1. 모든 조합을 만듬 2^15개 최대 2. for 모든 조합에 대한 시뮬레이션 수행, 그러나 불가능하면(일정 겹치거나, 안끝나는 것) 중간 종료 3. 매 시뮬레이션이 끝날 때, 수행 값의 최대를 업데.. 2020. 6. 16.
[백준 17143] 낚시왕 (C++) A. 문제설명 https://www.acmicpc.net/problem/17143 문제에 대한 자세한 설명은 링크 참조 1. 크기가 R*C인 지도가 존재 2. 해당 지도 위 각 칸에 상어가 존재하는데, 각각의 상어는 크기/방향/속력 정보를 가짐 3. 낚시왕은 처음 1열에 위치해있다가 오른쪽으로 한칸씩 이동하며 해당 열의 가장 상단의 상어를 잡는다. 4. 낚시 후 상어들이 현재 위치에서 주어진 방향으로 속도만큼 이동하는데, 여기서 벽을 만나면 방향은 반대로 바꾸고 속력을 유지한채로 이동한다. 5. 낚시왕이 끝열까지 이동하면서 잡을 수 있는 상어의 크기의 합 구하기 B. 접근법 시뮬레이션 낚시왕이 1~C 행까지 이동할 동안 상어의 이동 시뮬레이션 함수를 구현하여 움직임을 모사한다. 여기서 까다로운 점은 상어.. 2020. 6. 7.
[SWEA 9088] 다이아몬드 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Oktj6WMQDFAWY 문제에 대한 자세한 설명은 링크 참조 1. 각각 크기가 다른 N개의 다이아몬드가 존재 2. 이 중 몇개를 골라 선물을 하려고 한다. 3. 다이아몬드 묶음은 K개의 크기차이 이하인 것들이어야 함 4. 묶음 중 최대로 줄 수 있는 다이아몬드의 수를 구하라 B. 접근법 정렬 + Sliding Window 먼저 N개의 다이아몬드를 오름차순으로 정렬한다. 그 다음 head와 tail을 옮겨가며 Sliding Window를 이동하여 K개 이하의 차를 가지는 다이아몬드 묶음 윈도우를 만들어 정렬된 배열을 탐사. tail을 뒤로 옮길때마다.. 2020. 6. 2.
[백준 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.

티스토리툴바