Algorithm Study
[코드업 파이썬] # 3019 스케줄 정리
구조체 연습 # 3019 스케줄 정리 링크 : https://codeup.kr/problem.php?id=3019&rid=0 스케줄 정리 5 sleep 2014 05 23 golf 2014 06 02 travel 2015 11 22 baseball 2013 02 01 study 2014 05 23 codeup.kr 풀이 N = int(input()) li = [list(input().split()) for i in range(N)] li = sorted(li, key = lambda a : (int(a[1]), int(a[2]), int(a[3]), a[0])) for i in li: print(i[0]) lambda로 정렬할 때 데이터 형식(str 인지 int 인지)을 확인해야 한다 lambda 이후에..
[코드업 파이썬] # 3015 성적표 출력
구조체 연습 # 3015 성적표 출력 링크 : https://codeup.kr/problem.php?id=3015&rid=0 성적표 출력 첫째 줄에 데이터의 개수 $n$ ($3
[이코테 자료구조] 4. 정렬 알고리즘
정렬 알고리즘 by 나동빈님 링크 https://www.youtube.com/watch?v=KGyK-pNvWos 정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array..
[이코테 자료구조] 3. 스택/큐 자료구조, 재귀함수, DFS & BFS
DFS / BFS by 나동빈님 링크 https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정 DFS, BFS는 탐색 알고리즘에 해당 코딩 테스트에서 자주 등장하는 유형 스택 자료구조 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 입구와 출구가 동일한 형태 ex) 박스 쌓기, 플링글스 통 구조 삽입과 삭제로 진행, 시간복잡도 : O(1) stack = [] stack.append(n) stack.pop(n) 최상단 원소부터 출력하려면 stack을 역순으로 출력 큐 자료구조 선입선출 : 먼저 들어온 데이터가 먼저 나가는 형식 입구와 출구..
[백준 파이썬] # 1541 잃어버린 괄호
Silver II # 1541 잃어버린 괄호 그리디 알고리즘 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 a = input().split('-') # '-' 기준으로 분리 li = [] for i in a: cnt = 0 i = i.split('+') # 각 i를 '+' 기준으로 분리 for j in i: cnt += int(j) # 계산을 위해 숫자형으로 바꿔야 함 li.append(cnt) n = li[0] for i..
[백준 파이썬] # 1931 회의실 배정
Siver II # 1931 회의실 배정 그리디 알고리즘 유형 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 N = int(input()) time = [] for i in range(N): start, end = map(int, input().split()) time.append([start, end]) time = sorted(time, key = lambda a : a[0]) # start 기준으로 오름차순 정렬 time = sorted(time, key = lambda a : a[1]) # end 기준으로 오름차순 정렬 ## 오름차순 정..
[이코테 자료구조] 2. 그리디 알고리즘 & 구현
그리디 알고리즘 by 나동빈님 링크 : https://www.youtube.com/watch?v=2zjoKjt97vQ 그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 풀이의 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다 많은 코딩 테스트에서 제시되는 문제 유형 중 하나 ※ 예시 문제 : [거스름 돈, 곱하기 혹은 더하기, 모험가 길드] 최적의 해를 빠르기 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적..
[백준 파이썬] # 11047 동전 0
Silver II # 11047 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 N, K = map(int, input().split()) count = 0 coin = [] for i in range(N): A = int(input()) coin.append(A) coin = sorted(coin, reverse=True) for i in coin: count +=..
[이코테 자료구조] 6. 다이나믹 프로그래밍
다이나믹 프로그래밍 by 나동빈님 링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us&t=144s 메모리를 적절히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하는 것을 방지 두 가지 방식(탑다운, 바텀업)으로 구성 동적 계획법이라고도 부른다 다이나믹 프로그래밍의 '다이나믹'은 큰 의미 없이 사용된 단어 조건 문제가 다음의 조건을 만족 할 때 사용할 수 있다 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 할 때 피보나치 수열의 모든 가능성을 계산하려면 굉장히 많은 연산과정을..
[백준 파이썬] 소수 문제 유형 정복하기
파이썬 소수문제 정복하기 한 주간 알고리즘 스터디를 진행하면서 소수 문제를 다루었다. 소수가 사용되는 유형을 정리해두면 도움이 될 것 같아서 정리해보았다. 설명하기 쉬운 코드를 위해 유투브 영상을 일부 참고하였다. 성능 비교를 위해서 time을 측정하였고, input에는 동일하게 5를 넣어 비교해보았다. 소수 여부 판별 # chapter 1 # n이 소수인지 아닌지 판별_약수의 개수를 check 하여 판별 n = int(input()) check = 0 for i in range(1, n+1): # n+1 : n까지 포함하기 위해 ; range 범위의 특성 if n%i == 0: check += 1 if check == 2: print('소수') else: print('소수가 아닌 수') # 5 # 소수..