2차원 리스트는 다른 리스트 조작과 달리 max() 함수를 쓴다고 해서 바로 최대, 최솟값이 나오는게 아니다! -> map 함수를 이용하자 !! ex) 최댓값 구하기 arr = [ [1, 7, 12], [4, 7, 13], [1, 5, 17], [3, 5, 20], [2, 4, 24], [1, 4, 28], [3, 6, 37], [5, 6, 45], [2, 5, 62], [1, 2, 67], [5, 7, 73], ] max_value = max(map(max, arr)) print(max_value) ex) 최솟값 구하기 vertices = [ [1, 7, 12], [4, 7, 13], [1, 5, 17], [3, 5, 20], [2, 4, 24], [1, 4, 28], [3, 6, 37], [5, 6,..
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 전위, 중위, 후위 순회를 코드로 구현하는 문제이다. c++로 코딩하던 버릇이 남아있어 그런지 아스키 코드를 이용했다 원랜 ans 변수에 답을 담는 것이 아닌, visited 배열을 이용해 답을 저장하려고 아스키 코드를 썻는데 결국 그러진 않았다. 굳이..? 라는 생각이 들어서,, 트리의 순회 방법에 대해 알고 있다면 차례대로 구현해주기만 하면 된다. 좀 더 정석적인 풀이 방법이..
https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 상당히 까다롭게 풀었던 문제인데, 파이썬 후기가 없어서 글을 남긴다. 우선 시루의 위치에서 시작하여 bfs를 돌리며 매번 마네킹에 근접했는지 검사하는 방식으로 하려 했으나, 당연히 시간초과 및 자잘한 오류들이 많이 생겼다.. 해결하기 위해선, 마네킹들의 위치에서 bfs를 돌려 마네킹에 근접한 곳들을 따로 체크해둔다. 배열을 ..
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 일단 이 문제는 입력도 은근 까다롭기 때문에 ㅋㅋ 입력부터 잘 받아보자. 무방향이지만 아래 코드처럼 입력받을 필요는 없다! 어차피 입력값에서 다 주어지기 때문이다. tree[a].append((b,c)) tree[b].append((a,c)) 그리고 이 문제는 '트리의 지름' 이란 키워드에 대한 이해가 필요하다. 단순히 임의의 한 노드에서 가장 멀리 있는 노드를 구하는 것이 아니라..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net dp문제는 왜인지 항상 블로그에 글을 쓰고 싶게 만든다. 처음 이 문제를 보면, 점화식을 만드는 규칙이 한 눈에 보이지 않아 무척 당황스러울 것이다. 하지만 연습장 하나 꺼내서 차근차근 손으로 계산하다보면 어떤 규칙이 눈에 띌 것이다 ! 그 규칙은 바로 삼각형이 정삼각형, 역삼각형 꼴을 반복하는 것이고, n번째 삼각형의 변의 길이 = 바로 직전의 삼각형의 변의 길이 + 직전 삼각형을 만드는데 쓰였던 삼..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 간단한 dfs문제이다. bfs로도 풀 수 있지만 dfs 연습중이라 그냥 dfs로 풀었다 무방향이므로 양쪽으로 모두 다 입력받아주고, 방문하지 않은 노드에 대해서만 dfs 탐색을 진행해준다. dfs 탐색이 끝난다면, 하나의 '연결요소'에 대한 탐색이 끝난 것과 동일한 것이므로 정답 개수를 +1 해주면 된다! import sys sys.s..
