알고리즘
-
[백준] ⭐⭐ 4195 친구 네트워크백준 Online Judge 2021. 8. 26. 21:13
문제 설명 친구와 친구 간에 서로 연결된 네트워크가 있을 때, 총 몇 명이 연결 되어 있는가? 합집합을 찾는 문제 (Union-Find Algorithm) 재귀 함수를 이용하여, 연결된 네트워크를 찾고 또 찾는다. def find(x): if x == parent[x]: return x # 재귀 함수 형태로 부모 원소를 찾는다. else: p = find(parent[x]) parent[x] = p return parent[x] def union(x, y): x = find(x) y = find(y) # x, y의 부모 값이 다른 경우, y의 부모 값을 x의 부모 값으로 바꾼다. if x != y: parent[y] = x number[x] += number[y] test_case = int(input(..
-
[백준] 1920 수 찾기백준 Online Judge 2021. 8. 26. 20:31
문제 링크 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해설 문제: 주어진 정수 안에 찾는 정수가 존재 하는가? 힌트: set 자료형은 중복이 허용되지 않는 집합이다. 리스트 [] 튜플 () 값을 바꿀 수 없다. 딕셔너리 {key1:value1, key2:value2,..} 집합 set {} 중복값이 없다. 문제 풀이 코드 n = int(input()) array = set(map(int, input().split())) m = int(input()) ..
-
[백준] 5397 키로그백준 Online Judge 2021. 8. 25. 22:02
[백준] 5397 키로거 비밀번호 찾는 방법 두 개의 스택을 사용하면 쉽게 풀 수 있다 풀이 시간 최대 40분 test_case = int(input()) for _ in range(test_case): left_stack = [] right_stack = [] data = input() for i in data: # 지워야 할 때, 왼쪽 스택이 비웠는가 먼저 확인한 뒤 지운다. if i == '-': if left_stack: left_stack.pop() # 커서를 왼쪽으로 옮긴다 = 문자 하나를 오른쪽 스택으로 넘긴다. elif i == '': if right_stack: left_stack.append(right_stack.pop()) # 문자가 입력 된 경우 else: left_stack.app..
-
[백준] 1874 스택 수열백준 Online Judge 2021. 8. 25. 20:33
스택 수열 유형: 스택, 그리디 난이도: 하 스택에 push 할 때는 그 숫자를 넣을 때까지 삽입하면 된다. (예를 들어, 4를 넣고자 하면 1, 2, 3, 4를 넣는다). 스택에서 pop 하는 경우, 내림차순으로 빼낼 수 있는지 확인해야 한다. 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net n = int(input()) count = 1 stack = [] result = [] for i in range(1, n + 1): ..
-
[배열] 하 - 2920 음계 문제백준 Online Judge 2021. 8. 23. 18:31
2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 문제 요약 난이도 : 하 문제 유형 : 배열, 구현 추천 풀이 시간 : 15분 [문제 링크](https://www.acmicpc.net/problem/2920) 문제 해설 숫자 1~8까지 여러 개를 입력 받았을 때, ascending/descending/mixed로 분류하는 문제 입력 예시 : 1 2 3 4 5 6 7 8 출력 예시 : ascending 문제 풀이 코드 # 데이터를 입력 받는다. data_list = li..
-
[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)Algorithms & Data Structure 2021. 8. 22. 14:41
탐욕 알고리즘 최적의 값에 가장 가까운 값을 구하는 알고리즘이다. 알고리즘 예시: 동전 문제 4720원을 1원, 50원, 100원, 500원 동전으로 지불 할때, 가장 적은 동전의 개수로 지불하라. coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse = True) for coin in coin_list: coin_num = value // coin total_coin_count += coin_num value -= coin_num * coin details.append([coin, coin_num]) return total_co..
-
깊이 우선 탐색 (Depth-First Search)Algorithms & Data Structure 2021. 8. 20. 21:56
깊이 우선 탐색이란 그래프 탐색 알고리즘 노드의 자식들을 먼저 탐색하는 알고리즘 오른쪽 노드 먼저, 왼쪽 노드 먼저는 상관 없다. 구현하기 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def dfs(graph, start_node): visited, need_visit = list(), list() need_visit..
-
[알고리즘] 너비 우선 탐색 (BFS)Algorithms & Data Structure 2021. 8. 20. 18:23
너비 우선 탐색 (Breadth-First Search) 노드와 같은 레벨에 있는 형제 노드들부터 먼저 탐색하는 방식 그래프를 표현 할 때 딕셔너리와 리스트 자료 구조 활용 시간 복잡도 : O(V+E), (V: 노드 갯수, E: 간선 갯수) 알고리즘 구현 방법 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def bfs..