분류 전체보기
-
[백준] ⭐⭐ 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()) ..
-
[백준] 10930 SHA-256백준 Online Judge 2021. 8. 26. 19:19
문제 링크 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net 문제 해설 SHA-256은 대표적인 해시 알고리즘 중 하나이다. 문제 유형: 해시, 구현 추천 문제 풀이 시간: 15분 문제: 문자열 S가 주어졌을 때, SHA-256 해시값을 구하라. 풀이 코드 import hashlib input_data = input() # 입력받은 데이터의 바이트 객체를 구한다. encoded_data = input_data.encode() # hashlib의 sha256 함수를 사용해서 해쉬 객체를 만든다. result = hashlib.sha256(encoded_data).hexdigest..
-
[백준] 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): ..
-
[백준] 2798 블랙잭백준 Online Judge 2021. 8. 23. 19:53
2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 요약 문제 유형: 배열, 완전 탐색 난이도: 하 카드가 n개 만큼 있을 때, 그 중 3개의 카드 합이 총 m을 넘지 않을 때, 카드 3장의 합을 출력하라. 문제 코드 작성 모든 경우의 수를 모두 다 합한다. 카드 세 장을 뽑은 뒤 합한 값을 서로 비교해서 가장 큰 값을 출력한다. n, m = list(map(int, input().split(' '))) data = list(map(int, input().split(' '))..
-
[배열] 하 - 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..