이것 저것 올리는 곳

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 문제는 두 노드를 선택했을 때, 두 노드 사이의 지름의 길이가 최대가 되는 길이를 출력하는 문제다. 처음 문제를 풀기 위해서 접근한 방법은 두 노드 쌍을 모두 구하고, 여기에 대해서 DFS탐색을 통해 가장 긴 지름을 탐색해 봤다. 구현하면서도 너무 오래 걸릴 거라 생각했는데, 역시 시간초과가 났다. 오답 import sys sys.setrecursionlimit(2500)..

알고리즘 문제풀이 2023. 12. 20. 19:05

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 한동안 알고리즘 문제를 못 풀었었다.. 글씨도 눈에 안 들어오는 그런 기간이었다. 그런데 오랜만에 재밌는 문제를 풀었다. 문제를 풀기 위해서는 BFS알고리즘을 약간 응용하면 된다. 질문게시판 보니 DFS로 푸는 사람도 많은 것 같다. 문제를 계속 풀다 보니 DFS보단 BFS가 더 실용적이고 더 편한 것 같다. 물론 문제에 따라 다르겠지만. 문제 해결 방법을 설명하기 위해 백준에..

알고리즘 문제풀이 2023. 10. 16. 23:36

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 처음 문제를 봤을 때 감이 안 잡혔다.. 대충 어떻게 풀지 두 가지 방법을 생각해 냈는데, 1. 벽이 들어갈 수 있는 모든 경우 마다 bfs탐색을 하기 2. 바이러스를 퍼지게 하고, 막을 수 있는 공간이 딱 3이 나올 때를 체크하기 처음에 두번째 방법으로 풀어야겠다고 생각을 했는데.. 생각해 보면 해볼수록 답이 없는 방법이라는 걸 깨우치고 질문 게시판으로 달려갔다. 질문 게시판을 보니 combinatio..

알고리즘 문제풀이 2023. 9. 26. 19:07

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 구현 자체는 시간이 오래 걸리지 않았지만, 최적화할 때 질문 게시판에서 힌트를 얻었다. 자꾸 28%에서 시간 초과가 나왔었다. 문제는 1부터 시작해 100까지 갈 때, 주사위를 굴려서 간다. 그런데 뱀과 사다리가 있는데, 뱀은 현재 번호에서 뒤쪽으로 이동시키는 수단이고, 사다리는 현재 번호에서 앞쪽으로 이동시키는 수단이다. 뱀과 사다리의 위치와 ..

알고리즘 문제풀이 2023. 9. 24. 20:33

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제의 3차원 버전 문제다. 문제를 풀..

알고리즘 문제풀이 2023. 9. 23. 22:04

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 BFS공부 후에 처음으로 BFS응용? 문제를 풀어 봤다. 나의 문제 접근 방법은 지도에서 2가 나온 지점을 시작 지점으로 근처에 갈 수 있는 index번호들을 큐에 하나씩 넣어가며 탐색했다. 예시로 0, 0에서 갈 수 있는 index들은 [0,1], [1,0]이 있다. [0,1]에서 갈 수 있는 index들은 [0, 2], [1, 1]이 있고 [1..

알고리즘 문제풀이 2023. 9. 8. 23:10

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 BFS를 공부했다. BFS를 공부하기 전에는 BFS도 재귀 함수를 이용해서 구현하는 게 일방적인 방법일 거라고 생각했었다. 그런데 공부해보니 대부분 그냥 큐랑 반복문을 사용해서 구현하는 것 같다. 문제는 주어진 노드들이 어떻게 연결 되어 있는지 인접리스트를 만들어 주고, 입력에서 주어진 시작 노드를 기준으로 BFS, DFS 탐색하면 된다. 이 문제에서 주..

알고리즘 문제풀이 2023. 9. 7. 22:04

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 이진트리가 주어졌을 때, 리프 노드라는 것의 개수를 구하는 문제다. 나는 이 문제를 풀 때 입력으로 주어지는 부모 노드를 이용해 다음과 같이 인접 리스트를 만들어 준 후에 삭제할 노드를 삭제하고 리프 노드 카운팅을 해줬다. path = [[] for _ in range(n)] for i in range(n) : if node[i] == -1 : root_node = i else : pa..

알고리즘 문제풀이 2023. 9. 1. 23:37