기록 기록

정렬: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것, '알고리즘의 효율성' 정렬 알고리즘은 이진 탐색의 전처리 과정 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복. '매번 가장 작은 것을 선택' 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료 O(N^2) 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_inde..

꼭 필요한 자료구조 기초 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정. 대표적인 탐색 알고리즘 → DFS/BFS 스택: LIFO, 파이썬에서 스택 이용할 때에는 별도 라이브러리 사용할 필요 없이 기본 리스트의 append()와 pop() 메서드 이용 stack = [] stack.append(5) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 큐: FIFO, '공정한' 자료구조, 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조 활용 deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드 이용 from collections import deque queu..

Ch3 그리디 그리디 알고리즘 (= 탐욕법): '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 코딩테스트에서는 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. Ch4 구현 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

from itertools import permutations def solution(k, dungeons): answer = 0 for p in permutations(dungeons, len(dungeons)): temp = k count = 0 for need, spend in p: if temp >= need: temp -= spend count += 1 answer = max(answer, count) return answer permutations 통해 모든 순서 경우의 수 구하고 하나씩 실행해본 뒤 최대 던전 수 return하는 방식

def solution(brown, yellow): answer = [] a = [] for i in range(1, int(yellow ** 0.5) + 1): if yellow % i == 0: a.append([yellow //i, i]) for element in a: if 2*(element[0] + element[1]) + 4 == brown: answer.append(element[0] + 2) answer.append(element[1] + 2) return answer 문제를 풀기 위한 아이디어: yellow와 brown의 관계에 대해 생각해보면 간단하게 해결할 수 있음 yellow 격자가 x * y 형태로 놓여 있다면 brown = 2x + 2y + 4의 관계식을 가짐. yellow 격..

from itertools import permutations def solution(numbers): answer = [] nums = [n for n in numbers] per = [] for i in range(1, len(numbers)+1): per += list(permutations(nums, i)) new_nums = [int(''.join(p)) for p in per] for n in new_nums: if n < 2: continue check = True for i in range(2, int(n**0.5) + 1): if n % i == 0: check = False break if check: answer.append(n) return len(set(answer)) permut..

def solution(answers): supo_1 = [1, 2, 3, 4, 5] supo_2 = [2, 1, 2, 3, 2, 4, 2, 5] supo_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] supo_count = [0, 0, 0] for i in range(len(answers)): if answers[i] == supo_1[i % 5]: supo_count[0] += 1 if answers[i] == supo_2[i % 8]: supo_count[1] += 1 if answers[i] == supo_3[i % 10]: supo_count[2] += 1 k = max(supo_count) answer = [] if supo_count[0] == k: answer.append(..

def solution(sizes): big = [] small = [] for i in sizes: if i[0] > i[1]: big.append(i[0]) small.append(i[1]) else: big.append(i[1]) small.append(i[0]) answer = max(big) * max(small) return answer 명함 눕혀서 수납 가능 → 명함의 가로 길이, 세로 길이가 주어졌을 때 둘 중 더 큰 값과 작은 값으로 분류 큰 값들 중 max, 작은 값들 중 max 구해서 곱하기 대박 충격 위 내용을 두 줄로도 코딩 가능... def solution(sizes): return max(max(x) for x in sizes) * max(min(x) for x in sizes)