Door

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

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

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

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

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 이 문제는 구현하는 것도 어려운 편인데 상어의 위치나 냄새 등등을 어떻게 저장하는가도 어려웠습니다. 이 문제를 풀면서 좀 어렵다고 느끼긴 했지만 파이썬의 리스트활용에 대해서 많이 공부를 할 수 있었죠. 이 문제를 풀 때에는 deepcopy를 많이 이용했습니다. 이 문제가 구현이 힘든 이유는 '상어가 동시에 이동한다' '이동 후에 냄새가 지워진다' 라는 ..

알고리즘 공부 2022. 3. 27. 14:50

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 이 문제는 자리를 배치를 어떻게 해주냐가 관건이었습니다. 그런데 자리를 배치할려고 보면 처음에 어떻게 학생과 학생이 좋아하는 학생을 어떻게 받을 것인가에서 골치를 먹습니다. 저도 이런 류의 문제를 처음 풀 때 특히나 파이썬에 익숙하지 않았을 때는 C에서 어떻게 했지...만 생각하다가 입력부터 막힌 적이 있었습니다. 그러다가 계속 문제를 풀어가면서 '파이썬에서 이렇게 받는구나' 라는 감이..

알고리즘 공부 2022. 3. 26. 22:49

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 구역을 나누는 건 BFS류의 문제로 많이 풀어봐서 바로 BFS가 생각이 났습니다. 그 다음에 관건은 어떻게 분배를 해주냐는 거였습니다. 우선 BFS로 구역을 전부 구한 후 구역의 합과 구역의 크기를 구한 다음에 분배를 시켜줘야하는데 이건 BFS를 마치고 해야하는 작업이었죠. 저같은 경우에는 분배용 큐를 하나 더 만들어서 BFS를 하면서 분배용 큐에 구역의 위치들을 넣었습니다. 그리고..

알고리즘 공부 2022. 3. 26. 11:40

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 문제가 요구하는 것이 상당히 많고 배열도 큰 편이라 차근차근 푸는 게 중요했습니다. 이 문제에서는 격자를 돌려주는 것과 인접한 얼음을 보고 뺴주는 것 2개를 구현하는 것이 관건이었습니다. 먼저, 격자로 돌려주는 걸 먼저 볼까요?? 저는 컴퓨터에서 한줄 한줄씩 받고 돌려주는 경우를 생각했습니다. L=2인 격자인 경우를 생각하면서 문제를 그려봤습니다. 이걸 구현하기 위해 tmp에 ..

알고리즘 공부 2022. 3. 23. 23:48

https://programmers.co.kr/learn/courses/30/lessons/42895# 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제에서는 DP라고 유형으로 나눴지만 DP라는 걸 모르면 적잖이 당황하기 쉽습니다. 사실 뭐 DP라는 걸 알아도 풀기가 어렵지만... 이 문제를 풀 때 점화식 아이디어가 떠오르질 않아서 인터넷 풀이를 참고해봤습니다. 이 문제의 핵심은 'N을 몇 번쓰는가'입니다. 저는 처음에 무턱대고 사칙연산을 구할려고 달려들었습니다. 예를들면 N=5일 때 2의 값은 뭐고 3의 값은 뭐고... 이렇게해보니 규칙이 보이는듯한데... 코드로 구현해보니 상당한 분노가 올라왔습니다. 무엇보다, 55 555 5555이런건 어떻게 구하지? 라는 것이 머릿속을 떠나지 ..

알고리즘 공부 2022. 3. 17. 11:27