Door

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 이 문제는 이름 그대로 사람을 낚는 문제. 정답률이 25%이하인 문제치고 문제에서 요구하는 것이 어렵지 않아 보였습니다. 저도 요구하는 걸 다 나열해보고 '별거 아니네' 하고 넘어갔다가 시간초과가 떠서 참 애를 먹었습니다. 풀다보니깐 최적화라는 관점에서 문제를 공부하게 되었습니다. 구현할 건 크게 3가지 1. 낚시왕이 이동 2. 현재 위치한 열에서 가장 땅에 가까운 상어를 포획..

알고리즘 공부 2022. 4. 10. 23:19

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net easy하다는 문제명과 달리 그렇지 못한 문제. 이 문제는 DFS로 접근합니다. 상하좌우로 움직이는 경우가 있고 각각을 총 5번 움직이면 최대를 구합니다. https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-15683%EB%B2%88-%EA%B0%90%EC%8B%9C%ED%8C%8C%EC%9D%B4%EC%8D%AC..

알고리즘 공부 2022. 4. 10. 18:27

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현할 건 크게 2가지입니다. 1. 현재 택시지점 기준 가장 가까운 손님 찾아가기 2. 그 손님의 목적지까지 이동하기 여기에, 중간에 기름이 떨어지면 바로 영업종료를 해주는 것이 있죠. 저는 우직하게 BFS를 사용해서 택시를 기준으로 각각의 손님의 이동거리를 구했습니다. (중간중간에 벽이 있기 때문에 bfs로 길탐색을 해야합니다.) 그랬더니 예제는 다 맞았으..

알고리즘 공부 2022. 4. 10. 00:31

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 봄 여름 가을 겨울대로 문제에서 주어진 걸 적어보면 봄 나이가 어린 나무부터 양분을 먹음 나이만큼 양분을 먹고, 양분 못먹으면 죽음 여름 봄에 죽은 나무가 양분이 된다. 이 때, 죽은 나무//2만큼 양분이 생성 가을 나무나이가 5의 배수일 때 번식. 인접한 칸에 1인 나무 생성. 겨울 각 토양에 양분증가. 입력받았던 걸로 더 추가 첫번째부터 난관에 봉착합니다. 봄 여름 가을 겨울 ..

알고리즘 공부 2022. 4. 9. 10:35

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 상당히 요구하는 것이 많은 문제입니다. 단계별로 하나씩 차근차근 밟으면 되는데 여기서 가장 난감한 부분으 '첫번째 어항 쌓기'입니다. 저는 이걸 어항을 말아올린다고 표현했는데요 처음 문제를 푸는 입장에서는 저게 무슨 소리인지하고 난감해합니다. 애당초, 어떻게 리스트를 말아서 올리냐고요... 한참을 고민하던 저는 우직하게 문제에서 요구하는데로 말아올리는 걸 택했습니다. N*N행렬을 만들고 N-2열까..

알고리즘 공부 2022. 4. 9. 00:10

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 이 문제는 여타 길찾기 문제와는 다른점. 한번 움직이면 벽을 만날 때까지 이동한다는 것. 즉, 만약에 오른쪽으로 움직인다고 하면 벽을 만나기 전까지 계속 오른쪽으로 가야합니다. 이 문제에서 어려웠던 포인트는 1. 파란색이 구멍에 들어갈 땐 어떻게?? 2. 파란색공과 빨간색공이 겹치면 안되는데 이건 어떻게 구현하지?? https://wlstyql.t..

알고리즘 공부 2022. 4. 7. 23:23

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 이 문제에서 해결해야할 것은 1. 사다리 줄을 어떻게 구현할 것인가 2. 어떻게 사다리 줄을 추가로 그리는 걸 구현할 것인가 크게 두 개입니다. 문제에서 요구한 데로 저렇게 code로 구현하는 것이 가장 좋습니다. '만약에 줄이 이어지는 거니깐 예를들어 1 2 라인이 이어지면 1 1로 표현하는 거 어떤가요??' 실제로 제가 처음 문제를 접근했을 때 이렇게 구현을 시도했습니다. 저는 길찾기 문제에..

알고리즘 공부 2022. 4. 5. 23:11

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 저같은 경우에는 문제 예시는 다 풀었는데 제출해보니 시간초과로 헤매여서 인터넷의 도움을 받았습니다. 이 문제에서 풀어야할 것은 1. 바이러스 활성화시킬 케이스 구하기 2. 각각의 케이스별로 바이러스 활성화시키고 몇 초 걸리는지 계산하기 3. 그 중 최솟값 구하기 1은 백트레킹도 가능하지만 저는 이런 류의 문제에 대해서 바로 combination이 떠올랐습니다. 2022.03.24 - [알고리즘 공부] - ..

알고리즘 공부 2022. 4. 4. 00:03