전체 글 검색 결과
116 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 16719] ZOAC (python)

16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 재귀를 통해 작은 알파벳을 선택한다. 정답을 출력할 result 배열을 만든다. arr에서 제일 작은 알파벳을 찾는다. 해당 알파벳을 기준으로 뒷배열에서 또 작업을 한 뒤, 앞배열에서 작업을 한다. import sys input = sys.stdin.readline S = list(input().rstrip()) result = ['']*len(S) def func(arr, start): if not arr: return _min = min(arr) id..

2021. 5. 31. 03:49
개발/알고리즘

[백준 9934] 완전 이진 트리 (python)

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net BFS를 통해 해결하자! 배열의 중간값이 루트이고 루트를 기준으로 왼쪽 서브루트와 오른쪽 서브루트로 나눌 수 있다. makeTree함수를 통해 서브트리와 현재 깊이를 전달한다. import sys input = sys.stdin.readline K = int(input()) _input = list(map(int, input().split())) tree = [[] for _ in range(K)] def makeTree(arr, x):..

2021. 5. 31. 02:59
개발/알고리즘

[백준 9470] Strahler 순서 (python)

9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 위상정렬을 이용하여 푼다. [진입차수, 최대레벨, 최대레벨개수]를 나타내는 indegree 배열을 생성한다. 간선들은 ndict에 저장한다. 진입차수(indegree[i][0])가 0인 정점들을 queue 에 넣고 최대레벨(indegree[i][1])을 1로 설정해준다. queue에서 뽑아 해당 정점과 연결되어있는 정점들의 진입차수들을 1씩 낮춰주면서 최대레벨과 최대레벨개수를 갱신해준다. 만약 차수가 0이 된다면 최대레벨 개수가 2이상이라면 최대레벨을 1 올..

2021. 5. 31. 01:50
개발/알고리즘

[백준 15918] 랭퍼든 수열쟁이야!! (python)

15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net DFS로 모든 경우의 수를 체크해주면 된다. 2N+1 길이 arr 배열을 만든다. (default = 0) 해당 숫자를 사용했는지 안했는지 체크하는 N+1 길이 used 배열을 만든다. X와 Y자리 숫자는 항상 같으므로 arr[X] = arr[Y] = Y-X-1 로 설정한다. dfs함수를 통해 x가 2N+1이라면 수열이 완성된것이므로 count해준다. arr[x]가 0이 아니라면 이미 숫자가 들어있으므로 다음칸을 계산하는 dfs(x+1)을 실행한다. 숫자가 들어있지 않다면 사용하지 않은 숫자(j) 중에서 arr[x+j+1]에도..

2021. 5. 30. 19:32
개발/알고리즘

[백준 8980] 택배 (python)

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 알고리즘이다. 처음에는 시작점, 도착점을 기준으로 정렬을 했는데 도착점만을 기준으로 정렬을 해야했다. 1->5를 먼저하면 2->3, 3->4 와 같은 애들은 못할 수 있기 때문이다. 예시로 입력이 다음과 같을때 (도착점을 기준으로 정렬한 상태) 6 40 1 2 10 1 3 20 2 3 10 1 4 30 2 4 20 3 4 20 1. 마을들의 수용가능 박스수를 나타내는 box 배열을 생성한다. 1 2 3 4 40 40 40 40 2. 첫..

2021. 5. 29. 00:15
개발/알고리즘

[백준 14675] 단절점과 단절선 (python)

14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 연결되있는 선이 1개보다 많으면 단절점이 되고, 싸이클이 없는 트리이기 때문에 모든간선이 단절선이 된다. import sys input = sys.stdin.readline N = int(input()) arr = [0]*(N+1) for _ in range(N-1): s, e = map(int, input().split()) arr[s] += 1 arr[e] += 1 M = int(input()) for _ in range(M): fl..

2021. 5. 28. 19:07