Door

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/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 처음에 문제를 잘못읽고 저 블록들을 그림에 채워넣을 때 최대를 구하라는 뜻인줄 알고 이게 무슨 x같은 문제인가 욕하다가 아...하나만 하라고... 하면서 급 빵긋. 이 문제는 원초적으로 풀이하는 방법은 구현으로 모든 케이스를 구하는 경우입니다. 이 문제에서 가장 헷갈리는 부분이 생각보다 저걸 구현할 때 좌표가 헷갈릴 때가 많았습니다. 제가 구현한 아이디어는 얼추 맞았는데 (이렇게 맞았다고 생각했던..

알고리즘 공부 2022. 3. 26. 16:05

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://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 이 문제는 하얀색과 빨간색 두 개를 이동할 때 어떻게 구현할 것인가가 큰 관문이었습니다. 저는 저런식으로 알고리즘을 구성해봤습니다. 이 풀이방법은 list배열의 위치를 받아 기존 위치는 pop을 해주는 방식입니다. # 백준 17837번 새로운 게임2 N, K = map(int, input().split()) graph = [list(map(int, input().split())) for _ i..

알고리즘 공부 2022. 3. 23. 01:00

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 이 문제는 DFS로 푸는 아주 간단한 문제입니다. #점프 N=int(input()) graph=[list(map(int,input().split())) for _ in range(N)] x=0 y=0 count=0 def dfs(x,y): global count if graph[x][y]==0: count+=1 #print(count) return now=graph[x][y] if y+..

알고리즘 공부 2022. 3. 21. 18:18

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제의 길이가 매우 길므로 게리멘더링에 대해서만 집고 가겠습니다. 저런 식으로 경계를 만드는 건데 규칙은 이렇습니다. 저는 이런 순서대로 코드를 구현했습니다. 1. 4가지 경계선 먼저 그리기 2. 경계선 안에 5 선거구로 채워넣기 3. 나머지 구역에는 차례대로 1 2 3 4 넣기 처음에는 1 2 3 4 선거구를 넣은 다음에 나머지 구역은 선거구 5로 넣는걸로 구현했다가 원래 5로 넣어져야할 부분이 다른..

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