8 Days A Week

문제 주어진 N개의 동전으로 만들 수 있는 값 중 최소를 구하는 문제. 출처 - [이것이 코딩 테스트다] 교재 Q4 풀이과정 각각의 합으로 만들 수 있는 금액 중 최소를 구하는 데에 효율적인 구현이 생각나지 않았다. (1개~N개 동전을 모두 쓸 수 있는 점이 헷갈림) 모든 합계의 경우를 구하고 해당하지 않는 최소를 구할까 싶었지만 바람직하지 않음 정답 책에 기술된 내용 화폐를 기준으로 오름차순 정렬한다. 이후 1부터 차례로 특정한 금액을 만들 수 있는지를 확인한다. 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 우리는 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있..

bisect를 통해 이진탐색을 쉽게 구현할 수 있고 관련 기능을 사용할 수 있다. (그래도 이진탐색 코드 정도는 숙지하고 있도록 하자) bisect - Array bisection algorithm - Python 3.10.5 documentation from bisect import * li = [1, 2, 2, 3, 3, 4] print(bisect_left(li, 2)) # 1 print(bisect_right(li, 2)) # 3 print(bisect_left(li, 4)) # 5 print(bisect_right(li, 4)) # 6 insort(li, 2) print(li) # [1, 2, 2, 2, 3, 3, 4] bisect_left()는 찾고자 하는 값의 맨 처음 인덱스를 반환한다. b..

그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 우선순위 큐를 이용하는 다익스트라 알고리즘은 인접 리스트를 이용하는 방식이다. 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다. 최단 경로를 찾아야 하는 문제가 출제되었을 때, 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용할 수 있다. 반면에 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리하다. 서로소 집합 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합..

가장 짧은 경로를 찾는 알고리즘. 다익스트라 최단 경로 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다. 💡 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3과 4번을 반복한다. 다익스트라 알고리즘은 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한..

소수에 대한 알고리즘은 제대로 알아두는게 좋을 것 같다. [내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체) 이 글을 참고함 import math n=int(input()) nums=list(map(int,input().split())) sum=0 def is_prime_number(x): if(x

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에서 주로 파라메트릭 서치를 이용한다. 문7-3. # 이진 탐색을 이용한 파라메트릭 서치 문제 풀이 n, m = list(map(int, input().split())) array = list(map(int, input().split())) start = 0 end = max(array) #이진 탐색 수행(반복) result = 0 while(start mid: total += x - mid # 떡의 양이 부족한 경우 덜 자르기(왼쪽 부분 탐색) if total < m: end = mid - 1 # 떡의 양이 충분한 경우 더 자르기(오른쪽 부분 탐색) else: result = m..

순차탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트에 특정 값 원소가 있는지 체크할 때 count() 메서드 이용 시 시간 복잡도 O(N) #순차 탐색 소스코드 def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) target = input_data[1] print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은..

Selection Sort 매번 ‘가장 작은 것’을 선택해 앞으로 보낸다 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[min_index], array[i] print(array) 시간 복잡도: O(N^2) Insertion Sort 특정한 데이터를 적절한 위치에 ‘삽입’한다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 효율적이다. 삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 ..

재귀함수 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다. 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. → ex) DFS 반복문 대신에 재귀 함수를 이용하면 더 간결한 코드를 작성할 수 있다. DFS Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프는 노드(node)와 간선(edge)로 표현한다. 그래프의 두가지 표현방식 (연결이 되어 있지 않은 노드끼리는 무한(infinity)의 비용이라고 작성한다) 인접 행렬(adjacency matrix): 2차원 배열로 그래프의 연결 관계를 표현 INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를..

스택 선입후출(FILO), 후입선출(LIFO) 파이썬에서는 스택을 이용할 때 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 작동한다. 큐 선입선출(FIFO) 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용한다. deque는 스택과 큐의 장점을 모두 채택해 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. from collections import deque queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.popleft() print(queu..