본문 바로가기

정렬/탐색34

[정렬/탐색] 백준 25305 커트라인 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net 2. 문제 풀이 응시자 수 N명의 점수와 수상자 수 K명이 주어집니다. 상을 받는 커트라인 점수는 몇 점인지 구해야 합니다. 3. 코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) score = list(map(int, input().split())) score.sort() print(score[n-k]) 단순 정렬 문제입니다. 오름차순으로 정렬한 뒤, n-k+1번째 학생의 점수를 출력합니다. 2022. 12. 12.
[탐색/밸만포드] 백준 1865 웜홀 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 2. 문제 풀이 음수 가중치를 갖는 사이클(음수 사이클)이 있는 지 탐색하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 밸만 포드 알고리즘 def bf(start): dist = [10001] * (N + 1) dist[start] = 0 # 밸만포드 알고리즘 for i in range(N): for e in edge: start_node, next_.. 2022. 11. 2.
[탐색/DFS] 백준 1967 트리의 지름 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 문제 풀이 트리의 양 끝단의 거리를 재는 문제입니다. 즉, 가장 먼 노드 간의 거리를 재야 합니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를.. 2022. 10. 18.
[탐색/자료구조] 백준 1991 트리 순회 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 2. 문제 풀이 주어진 트리를 '전위', '중위', '후위' 탐색하는 문제입니다. 전위 순회: 중간 -> 왼쪽 -> 오른쪽 중위 순회: 왼쪽 -> 중간 -> 오른쪽 후위 순회: 왼쪽 -> 오른쪽 -> 중간 자료구조 단골 시험문제죠. "주어진 트리를 전위/중위/후위 순회하시오." 전위와 중위는 탐색 경로는 같으나, '방문'하는 시점이 다릅니다. '전위'는 루트부터 찍고 왼쪽 오른쪽을 탐색하고, '중위'는 .. 2022. 9. 21.
[문자열/탐색] 백준 14425 문자열 집합 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 2. 문제 풀이 문자열로 이루어진 집합 S가 주어집니다. 이후 주어지는 문자열 중 집합 S에 포함되는 개수를 출력합니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N, M = map(int, input().split()) S = set() # 집합 S for _ in range(N): S.add(input().rstrip()) # 같은 단.. 2022. 8. 21.
[정렬/브루트포스] 백준 1015 수열 정렬 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 2. 문제 풀이 길이가 N인 수열이 주어집니다. 수열 내에서의 대소관계를 파악해서, 작은 수부터 0 ~ N-1까지 순위를 매깁니다. 입력: 2 3 1 => 제일 작은 수 1은 '0'번 => 두번째로 작은 수 2는 '1'번 => 제일 큰 수 3은 '2'번으로 순위가 매겨집니다. 출력: 1 2 0 만약 같은 숫자가 있다면, 왼쪽에 있는 숫자가 순위가 낮습니다. 3... 2022. 8. 18.
[탐색/다익스트라] 백준 18352 특정 거리의 도시 찾기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 2. 문제 풀이 X 도시로부터 최단거리가 K인 도시를 찾는 문제입니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는.. 2022. 6. 29.
[이진/이분탐색] 백준 2512 예산 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 2. 문제 풀이 제한된 예산 내에서, 줄 수 있는 최대의 예산을 구하는 문제입니다. 2022.02.10 - [Algorithm] - [정렬/탐색] 백준 2805 나무 자르기 - Python [정렬/탐색] 백준 2805 나무 자르기 - Python [ Contents ] 1. 문제 (링크 참조) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1.. 2022. 6. 23.
[정렬/탐색] 백준 11931 수 정렬하기 4 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 문제 풀이 숫자를 입력받고, 내림차순으로 정렬 후 출력하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N = int(input()) numlist = [] for _ in range(N): numlist.append(int(input())) # 정렬 numlist.sort(reverse=True) # 출력 for i in numlist: .. 2022. 6. 21.

티스토리툴바