원준킹의 알고리즘 공부

문제 1. 럭키 스트레이트 (난이도 1, 풀이시간 5분/20분, 정답) #4:45 N = input() left_list = list(map(int,N[:(len(N)+1)//2])) right_list = list(map(int,N[(len(N)+1)//2:])) left_sum = sum(left_list) right_sum = sum(right_list) if left_sum == right_sum: print('LUCKY') else: print('READY') - 나눗셈(/) 연산 후엔 정수형이 아니라 실수형이라는 걸 명심해두길 문제 2. 문자열 재정렬 (난이도 1, 풀이시간 20분/20분, 정답) #4:58 S = list(input()) num = 0 for x,y in enumerate(S..

문제 1. 곱하기 혹은 더하기 (난이도 1, 풀이 시간 19분/30분, 정답(추정)) #6:31 50 #문자열 s : 0~9로 이뤄짐 #숫자사이에 x + 넣으며 연산가능 최대값 , + x 사이 우선순위없음 #결과는 항상 20억 미만 data = list(map(int,input())) # 2 9 0 8 4 # 0이 왼쪽 끝에 있을 때: 오른쪽이랑 + # 0이 오른쪽끝 : 왼쪽이랑 + # 0이 가운데: 0이 이전 인덱스에 있고 현재가 0이 아니면 + #0 + 2 #0 + 2 + 2 # #0 + 2 + 0 + 2 x 2 res = 0 for x,y in enumerate(data): if x == 0 and y == 0: continue elif x == len(data)-1 and y == 0: conti..

최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘 - 길 찾기 문제 - 다양한 사례 ex - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 - 그래프를 이용 / 노드 : 지점, 간선 : 경로 다익스트라 - 가장 비용이 적은 노드를 선택하는 과정 반복 (= 그리디 알고리즘) - 작동 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신 5. 3, 4 반복 1. 출발 노드 설정 노드 번호 1 2 3 4 5 6 거리 0 INF INF INF INF INF - 1에서..

다이나믹 프로그래밍 (동적 계획법) - 메모리 공간을 조금 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 사용조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 재귀적 구현 dyna = [0] * 100 def pibo(x): if x == 1 or x == 2: dyna[x] = 1 return 1 elif dyna[x] != 0: return dyna[x] else: dyna[x] = pibo(x-1) + pibo(x-2) return dyna[x] print(pibo(99)) - 탑다운(메모이제이션, 캐싱, 하향식) 방식 : 큰 문제를 해결하기 위해 순차적으로 작은 문제를 호출하며 해결하는 방식 반복적 구현 dy..

순차 탐색 - 데이터를 찾기 위해 앞에서부터 하나하나 차례대로 확인하는 방법 - WORST CASE 에는 O(N) 이진 탐색 - 데이터가 정렬되어 있을 때 사용 가능 - 매우 빠르게 데이터 탐색 가능 - 시작점,끝점 가운데의 중간점의 데이터와 찾고자 하는 데이터를 비교하여 범위를 좁혀나가는 방법 - 탐색 범위가 클 때(2000만을 넘거나 데이터 개수가 1000만 단위 이상이면) 재귀함수로 구현 data = [0,2,4,6,8,10,12,14,16,18] def binary_search(start,end,val,data): mid = int((start + end)/2) #print(mid) if val == data[mid]: print("result:",mid) return mid elif val < ..

정렬 - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 정렬 알고리즘으로 정렬 시 이진 탐색이 가능 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 선택 정렬 - 맨 앞의 데이터와 나머지 데이터 비교해서 작은 것을 맨앞으로 교체 반복, 그 다음 데이터들도 같은 작업 반복 - 가장 원시적 - O(N^2) , 2중 반복문으로 탐색 시 대략 O(N^2) 삽입 정렬 - 첫 원소는 정렬되었다고 판단하고 그 다음 원소부터 검사, 정렬된 원소들과 비교해서 위치를 찾아 삽입 - 중간과정에도 정렬 되어있음 - O(N^2), 2중 반복문 - BEST CASE 에서는 O(N) 퀵 정렬 - 기준 데이터(피벗)를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자 - 1. 첫번째 데이터가 피봇, 피봇 제외하..

탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - DFS/BFS 자료구조 - 데이터를 표현하고 관리하고 처리하기 위한 구조 - 스택 : FILO , 파이썬 리스트 그대로 사용 - 큐 : FIFO , collections 모듈에서 제공하는 deque 자료구조(데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적), deque.popleft() - 오버플로 : 삽입 시 저장 공간을 벗어나 데이터가 넘침 - 언더플로 : 데이터가 없는 상태에서 삭제 연산 시 그래프 - 노드(node), 간선(edge), 정점(vertex) - 표현방식 - 노드 0에서 노드1까지 거리 7, 노드2까지 거리5 - 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 [[0,7,5], [7,0,INF], ..

구현 - 머릿속의 알고리즘을 소스코드로 바꾸는 과정 - 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 - int 자료형 데이터 리스트 길이 10,000,000 == 메모리 사용량 약 40MB - 일반적으로 2000만번의 연산 == 실행시간 1초 - 데이터 개수가 100만개 -> O(NlogN) == 2000만번 연산 문제1. 상하좌우 #상하좌우 2020-12-16 16:42 시작 16:53 종료 N = int(input()) lis = input().split() pos = [1,1] for i in lis: if i == "L": if pos[1] != 1: pos[1] -= 1 elif i == "R": if pos[1]..

그리디 알고리즘 - 현재의 선택이 후에 끼칠 영향은 고려 안하고 매순간 최고의 선택만 하는 알고리즘 - 효과적, 직관적 / 최적의 답을 찾기에는 별로 - 바로 문제 유형 파악이 어려우면 그리디 알고리즘 의심 문제1. 큰 수의 법칙 #큰 수의 법칙 2020-12-15 17:10 시작 17:21 종료 N,M,K = list(map(int,input().split())) list = list(map(int,input().split())) list.sort(reverse=True) res = 0 cnt = 0 for i in range(0,M): if cnt == K: res += list[1] cnt = 0 else: res += list[0] cnt += 1 print(res) 문제2. 숫자 카드 게임 N,..