amaranthine

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs 구현 문제로, 이 문제를 풀 때 주의해야할 점이 몇 가지 있다. 1. 아기 상어의 위치를 나타내주는 9를, 아기상어를 찾은 즉시 0(빈칸)으로 바꿔주어야 한다. 그렇지 않으면 9 크기의 물고기가 있다고 인식해버린다. 2. 먹을 수 있는 물고기를 저장하는 리스트를 따로 만들어서 거리가 같은 모든 물고기를 넣어야 하며, 물고기가 위치한 거리보다 먼 곳은 탐색하지 않도록 조건을 제대로 주..

https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 통나무를 받은 순서대로 통나무의 번호가 매겨지므로, 통나무를 받을 때 좌표와 함께 idx를 저장한다. 그러면 통나무 리스트에는 [x1, x2, y, 통나무 번호]가 들어있게 된다. 이렇게 받은 리스트를 통나무의 x1 (제일 첫부분 좌표)로 정렬해준다. 만약 [[4, 9, 3, 0], [3, 5, 7, 1], [1, 3, 5, 2]] 과 같은 arr가 만들..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 제목 그대로 MST를 구하면 되는 문제이다. 처음에는 prim을 이용해 구현했는데 시간초과, 메모리초과가 나길래 크루스칼로 바꿔 풀었다. import sys input = sys.stdin.readline def find_p(x): if x != team[x]: team[x] = find_p(team[x]) return team[x] else: ret..

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 크루스칼을 이용해 간단하게 풀 수 있다. 만약 해당 노드끼리 성별이 같으면 continue로 넘어가주고, 성별이 다르다면 이어준다. edge_num으로 이어진 간선의 개수를 세어주고, 중간에 모든 정점이 이어지면 break를 해준다. 만약 주어진 간선을 이용해 정점을 이었는데도 모든 정점이 이어지지 않았다면 edge_num의 개수를 체크하여 -1, 모두 이..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온-파인드로 풀었다. 역시나 부모 찾기는 경로 압축을 이용했다. 입력이 좀 이상하게 주어져서.. 코드가 더럽게 나오긴 했지만.. 일단 주어진 사람들끼리 union 해주고, 진실을 아는 사람이 없으면 파티의 개수를 바로 출력한다. 진실을 아는 사람이 한명이라도 있다면, 진실을 아는 사람이 속한 집합(부모)를 set()에 넣어주고, 파티에 참석한 사람들이 속한 집합을 for문을 돌며 하나씩 확인해준다. 만약..

https://www.acmicpc.net/problem/17352

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 재귀를 이용한 조합으로 풀었다. 해당 행을 모두 0으로 바꾸고 재귀를 타고 들어가거나, 1로 바꾸고 재귀를 타고 들어가거나 원상 복귀 시키고(아무것도 하지 않고) 다음 행으로 넘어가는 식으로 풀면 된다. 처음에는 원상복귀 시키고 또 재귀를 타고 들어갔는데, 굳이 그렇게 해주지 않아도 for 문을 돌기 때문에 원상복귀한 상태 (아무것도 하지 않은 상태)로 다음 행으로 넘어간다. 이는 상태 트리를 그려..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 출발지부터 상하좌우 순서대로 탐방하며 각 정점으로 향하는 최단 거리를 갱신하면 되는 문제이다. 출발지를 중심으로 연결된 모든 점을 탐색하므로 DFS를 이용하였으며, 중간에 최단 거리가 갱신되어 큐에 저장된 정보를 이용할 필요가 없으면 (해당 정점을 거치는 것이 최단 거리가 아니라면) 다음 정점으로 넘어가 최단 거리를 계속 갱신하면 된다. from collections import deque dy =..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 브루트포스를 이용하여 모든 경우의 수를 다 살펴봐야 하는 문제이다. 처음에는 greedy, 혹은 bfs로 푸는 방법을 생각했는데 그냥 치킨집 위치와 집 위치를 각각 저장한 뒤, 치킨집 조합을 기준으로 집 위치를 모두 탐색하며 맨해튼 거리를 갱신해주면 되는 문제였다. 어렵게 생각하면 정말 어려운 문제다.. 조합은 itertools로도 만들 수 있으나, 재귀 연습을 위해 재귀로 ..

최소 값을 갱신해야 하는 문제를 해결할 때 보통 초기값을 0xfffff 혹은 9e10 등으로 표현하곤 했는데, 이번에 더 확실하게 무한대의 값으로 표기할 수 있는 방법을 알게 되었다. 양의 무한대 INF = float('inf') inf 로 표기가 되며, 위와 같이 아무리 큰 수를 가져와도 float('inf') 값이 더 큰 것을 알 수 있다. 음의 무한대 INF = float('-inf') 음의 무한대 또한 아무리 작은 수를 가져와도 float('-inf')값이 더 작은 것을 알 수 있다.