본문 바로가기

정렬/탐색34

[정렬/탐색] 백준 2693 N번째 큰 수 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 2. 문제 풀이 10개 수 중 세번째로 큰 수를 구하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 T = int(input()) for _ in range(T): numlist = list(map(int, input().split())) # 정렬 numlist.sort() # 세 번째로 큰 값 출력 print(numlist[7]) 단.. 2022. 6. 14.
[정렬/탐색] 백준 11728 배열 합치기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 2. 문제 풀이 두 배열을 합친 뒤, 정렬하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline # 입력 N, M = map(int, input().split()) numlist = list(map(int, input().split())) numlist.extend(list(map(int, input().split()))) # 정렬 numl.. 2022. 6. 9.
[탐색/다익스트라] 백준 11779 최소비용 구하기 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 문제 풀이 최소의 버스비용으로 A에서 B로 이동하는 문제입니다. 최소비용과 경로를 출력해야 합니다. 2022.05.17 - [Algorithm] - [탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python) 이전 문제인 '최소비용 구하기'에서, '경로 출력'이 추가되었습니다. 다익스트라 알고리즘으로 최적 거리를 찾은 뒤, 역추적해서 경로를 출력해야 합니다. 202.. 2022. 5. 18.
[탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 문제 풀이 최소의 버스비용으로 출발지에서 도착지로 이동해야 합니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라의 이론적.. 2022. 5. 17.
[탐색/다익스트라] 백준 1504 특정한 최단 경로 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 2. 문제 풀이 1번 정점에서 N번 정점으로 가는 최단 거리를 구하는 문제입니다. 단, 정점 v1, v2를 꼭 지나야 합니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지.. 2022. 5. 16.
[탐색/다익스트라] 백준 1753 최단경로 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 문제 풀이 시작점에서 다른 모든 노드로의 최단 거리를 구하는 문제입니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라.. 2022. 5. 15.
[탐색/DFS] 백준 11725 트리의 부모 찾기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 주어진 트리의 루트를 1이라고 했을 때, 각 노드의 부모를 구해야 합니다. 예제 입력 1번을 살펴보겠습니다. 트리의 루트를 1번으로 했을 때, 정렬하면 오른쪽과 같습니다. 사실 보기 좋게 만들기 위해서 오른쪽으로 정렬해둔 것이지, 컴퓨터 입장에서는 둘 다 같습니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접.. 2022. 5. 3.
[정렬/탐색] 백준 3273 두 수의 합 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 2. 문제 풀이 서로 다른 양수로 이루어진 수열에서 두 수를 뽑아 X가 되는 경우를 찾는 문제입니다. 1 2 4 6 7 8 10 s e 오름차순으로 정렬하고, 양 끝을 가리키는 포인터를 이용해서 X를 탐색합니다. start 포인터는 0번부터 시작해서 +1씩 증가하고, end 포인터는 n-1번부터 시작해서 -1씩 감소합니다. list[start] + list[e.. 2022. 4. 18.
[정렬/탐색] 프로그래머스 K번째 수 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 2. 문제 풀이 주어진 배열의 일정 범위 내 K번째 수를 구하는 문제입니다. sorted(lst): lst 내 원소를 오름차순으로 정렬 파이썬의 sorted() 함수를 이용하면 쉽게 구할 수 있습니다. 3. 코드 def solution(array, commands): answer = [] for i, j, k in commands: answer.append(sorted(array[i-1:j])[k-1]) return answer sorted() 함수를 사용해서 해당 범위의 배열을 .. 2022. 4. 17.

티스토리툴바