Door

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

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

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀이 움직이는 걸 표현하는 문제입니다. 여기서 구현할 포인트는 뱀의 몸통과 이동시의 뱀의 몸통입니다. 저는 이걸 구현하기 위해 deque의 appendleft와 pop을 사용했습니다. deque에서 맨 앞이 머리쪽이고 맨 뒤가 꼬리라고 놓고 생각했습니다. 문제를 읽어보면 사과가 있으면 머리만 움직이고 사과가 없으면 꼬리가 위치한 칸을 비워준다고 되있습니다. 사과가 있던 없던 움직이면 deque앞에 app..

알고리즘 공부 2022. 4. 3. 21:41

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이 문제는 dfs를 통한 백트레킹 cctv구현 이 두가지를 해야해서 체감 난이도는 높았습니다. 우선, 난감해보이는 cctv구현. 보통 저렇게 모드가 여러가지가 있다면 한 리스트에 모든 cctv를 구현해줍니다. 저같은 경우에는 mode=[[], [[1],[2],[3],[4]], [[1,3],[2,4]], [[1,2],[2,3],[3,4],[4,1]], [[1,2,3],[1,2,4],[2,..

알고리즘 공부 2022. 4. 3. 12:06

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 우선 그림을 보자마자 이게 뭔가 싶은 문제입니다. 보통 길찾기문제라면 좌표평면이라든가 사각형좌표로 많이 있는데 이건 뭐지... 싶었던 문제. 말을 움직이는 케이스는 dfs로 풀면 됩니다. 2022.03.06 - [알고리즘 공부] - [백준 14888번] 연산자 끼워넣기 [백준 14888번] 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ ..

알고리즘 공부 2022. 4. 2. 11:18

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 이 문제는 가장 큰 블록을 찾는 것이 가장 어려웠습니다. 저는 쌩쇼를 하다가 결국 서렌을 치고 솔루션을 보고나서야 아...내가 여태까지 뻘짓을 했다는 사실을 받아드렸죠. 저의 뻘짓을 먼저 나열하자면 1. 처음부터 큰 블록을 구한 뒤 비교하려고 했다 2. 우선 큰 블록을 구하는 알고리즘을 작성한 뒤에 이전의 큰 블록과 비교하는 식으로 구함 3. 문제의 조건에 맞춰서 큰 블록비교 이렇게 푸니깐 여..

알고리즘 공부 2022. 3. 31. 23:39

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제의 예제4를 쭉 캡처해봤습니다. 이 문제를 풀 때 해결해야할 포인트 1. 원판돌리기 2. 같은 거 지워주기 3. 평균구한 후 더하거나 뺴기 1은 문제 경험이 있다면 비교적 간단합니다. '어떻게 리스트를 돌리지? 으...복잡해' 물론 리스트를 직접 돌려도 괜찮지만 실수를 간혹하실 수 있습니다. 그래서 간단하게 원판을 deque로 받은 이후에 rotate()를 사용했습니다. 물론 ..

알고리즘 공부 2022. 3. 29. 21:59

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 이 문제같은 경우에는 나동빈님이 쓰신 이것이 코딩테스트다에 수록된 DP 대표유형에 속한 문제입니다. 처음에 문제의 풀이를 쭉 따라가도 이게 뭔소리지 하다가 직접 코드를 몇 번 쳐보고서야 이게 이런 의미이구나를 깨달았습니다. 이 문제를 DP로 풀기위해 이렇게 테이블을 쭉 그려봤습니다. 예시의 케이스를 가져와봤습니다. 동전 1이 있으므로 1부터 4까지 하나씩 증가하다가 ..

알고리즘 공부 2022. 3. 28. 18:43

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 이 문제는 다소 불친절해서 풀기가 힘들었습니다. 보통 문제에서 예시로 어떻게 이동하는지 보여주는데 이건 그런게 없어서 개인적으론 불친절하다고 느꼈네요. 저는 접근할 때 지도에 한꺼번에 파이어볼의 좌표를 다 그리고 이동과 나누기 두 개를 시행했습니다. 그리고 이동을 할 때 복사 후 저장하는 방식을 사용했습니다. 바로 원본에서 이동하면 저렇게 잘못동작할 수 있습..

알고리즘 공부 2022. 3. 27. 20:25