본문 바로가기

computer science/algorithm

(11)
sorted, sort() 문제를 풀다 보니, 당연히 sort()로 정렬해 반환할 수 있을 거라 생각했던 부분에서 None값이 나와 당황했다. 하지만 잘 생각해보니 sort()는 리스트 자체를 바꾸는 거고, 그걸 반환하려면 정렬 뒤 리스트를 반환하는게 맞구나.. 싶었다 1. 리스트명.sort() : 리스트형의 메소드이며, 리스트 원본 값을 직접! 수정함 . 반환 값은 None으로 정렬 값이 반환되지 않기 때문에 사용에 주의해야함 # 프로그래머스, 문자열 내 마음대로 정렬하기 def solution(strings, n): return strings.sort(key=lambda x:(x[n],x)) print(solution(["sun", "bed", "car"],1)) # 반환값 없음 2. sorted(리스트명) : 내장 함수로, ..
큐에 (), []로 추가할 때의 시간 차이 문제를 데크를 이용해 푸는데, 요소를 [A[i],i]로 추가하면 시간 초과가 나고 (A[i],i)로 추가하면 시간 내로 정답이 떴다 아직 이유를 못 찾아서 남겨둠! # [A[i],i]로 시간 초과 from collections import deque import sys input = sys.stdin.readline n,l = map(int,input().split()) A = list(map(int,input().split())) q = deque() for i in range(n): while q and q[-1][0] > A[i]: q.pop() q.append([A[i],i]) if q[-1][1] - q[0][1] >= l: q.popleft() print(q[0][0],end=' ') # (A..
[boj 11725] 트리의 부모 찾기 재귀 DFS, 비재귀 DFS, BFS로 구현해봤다. import sys input = sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) n = int(input()) tree = [[] for _ in range(n+1)] parent = [None for _ in range(n+1)] for _ in range(n-1): u,v = map(int,input().split()) tree[u].append(v) tree[v].append(u) # # 재귀 DFS 구현 # def DFS(graph,vertex,visited): # for i in graph[vertex]: # # 만약 아직 방문하지 않았다면 # if n..
Greedy (그리디, 탐욕 알고리즘) = 매 순간, 눈 앞에 보이는 것 중 최선의 선택을 하는 알고리즘 = 지역적 최적해(Local optima)가 결국 전역 최적해(Global optima)가 되는 알고리즘 큰돌의 터전 추천 전략 더보기 그리디로 문제를 풀려면 1) 최적부분구조(optiomal substructure). 지금 가장 최적인 답이 결국 전역 최적해가 되야함 2) 탐욕적 속성이 증명 되어야함. 보통 귀류법으로 증명 하지만, 위 방법을 코테에서 생각하는건 불가능... 현실적으로 그리디로 문제를 풀려면 1) 항상 그 지점 idx에서 가장 최적의 로직은 뭘까? 생각함. 유연성 필요! → 경우의 수를 따지기엔 너무나 큰 시간복잡도 또는 공간복잡도가 있다면 시도하는 알고리즘으로 생각하기 2) 그리디는 과거에 뭘 선택했는지 중요하지 않음...
sorting (정렬) 정렬(sorting)이란? 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 - 정렬은 프로그램 작성 시 빈번하게 필요로 함 - 다양한 알고리즘이 고안되어 있음. 위키피디아에 sorting algorithm 문서를 보면 거의 30개 가까이 있음 1. 버블 정렬(bubble sort) 앞에서부터 인접한 두 원소를 보면서 앞 원소가 뒤 원소보다 클 경우, 자리를 바꾸는 것을 반복함 → 자연스럽게 제일 큰 것부터 오른쪽에 쌓이게 됨 def bubbleSort(array): length = len(array) for i in range(length-1): for j in range(0, length-i-1): if array[j] > array[j+1] : array[j], array[j+1] = ..
Dynamic Programming (동적 계획법) 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 원리 1) 큰 문제를 작은 문제로 나눈다. 2) 작은 문제들이 반복되어 나타나고 사용되며, 작은 문제들의 결괏값은 항상 같아야 한다. 3) 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다 → ★memoization★ 4) 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다. 코드 예시 def fibo_dp(n): cache = [0 for idx in range(n+1)] # memoization cache[0] = 0 cache[1] = 1 for idx in range(2,n+1): cache[idx] = cache[idx-1] + cache[i..
알고리즘 복잡도 - 공간 복잡도 시간 복잡도는 얼마나 빠르게 실행 되는지를 나타내는 척도라면, 공간 복잡도는 얼마나 많은 저장 공간이 필요한지를 나타내는 척도다. 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이겠지만 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선된다. 따라서 알고리즘은 시간 복잡도가 중심이다. 또한 현업에서 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있다. 공간 복잡도란? 프로그램을 실행 및 완료하는데 필요한 저장 공간의 양을 의미(=입력의 크기와 문제를 해결하는데 걸리는 공간의 상관관계) 공간 복잡도라는 개념보다는, 512MB가 int 변수를 대략 1.2억개 정도 담을 수 있다는 개념을 가지고 문제에 임하는 것이 좋음 고정 공간(알고리즘과 상관없이 코드..
알고리즘 복잡도 - 시간 복잡도 1. 시간 복잡도 표기법 빅-오메가(Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타(𝚯(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 import random findNumber = random.randrange(1,101) # 1~100 사이의 랜덤값 생성 for i in range(1,101): if i == findNumber: print(i) break 예제 코드의 시간복잡도는 빅-오메가(Ω(n)) : 1번 빅-세타(𝚯(n)): N/2번 빅-오(O(n)): N번 코딩 테스트에서는 빅-오를 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는 1개의 테스..