❗0-1 배낭 문제란?0-1 배낭 문제는 각 물건을 한 번만 선택하거나 아예 선택하지 않는 문제로 중복 선택이 불가하며 물건을 0번(선택하지 않음) 또는 1번(선택함) 선택할 수 있기 때문에 0-1이라는 이름이다. 최대 용량을 넘지 않으면서 가치의 합이 최대가 되도록 선택하는 방법이다. ❗예제배낭의 최대 용량: k = 5물건의 정보 무게가치물건123물건234물건345 물건1의 무게가 2이므로 용량이 2 이상일 때부터 넣을 수 있다. w=2 ~ w=5까지 물건1을 넣었기 때문에 3으로 갱신한다. 물건2의 무게는 3이기 때문에 w=3부터 w=5까지 넣을 수 있다. 이때 w=3, 4의 경우 물건1을 넣은 가치인 3보다 물건2을 넣은 가치 4가 더 크기 때문에 4로 갱신해 준다. w=5의 경우는 물건1의 무게 ..

❗Dijkstra(다익스트라)란?다익스트라(Dijkstra) 알고리즘은 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이며 가중치가 있는 양의 가중치 그래프에 사용된다.   ❗다익스트라 알고리즘의 원리초기 설정:시작 노드에서 모든 노드까지의 최단 거리를 저장하는 배열(distance)을 생성하고 모든 거리를 무한대로 초기화시작 노드의 거리는 0으로 설정우선순위 큐 사용:시작 노드부터 출발하여 우선순위 큐(또는 최소 힙)에 현재 거리가 가장 짧은 노드를 선택하여 탐색을 진행매번 가장 짧은 거리를 가진 노드를 선택해 그 노드의 인접한 노드들을 확인최단 거리 갱신:현재 노드에서 인접 노드로 가는 거리가 기존에 기록된 거리보다 짧으면 distance 배열을 갱신갱신된 정보를 큐에 추가하여..

❗달팽이 배열나선형으로 배열을 채우는 패턴으로 배열을 돌면서 값을 순서대로 채우는 배열을 말한다. 일반적으론 왼쪽 상단에서 시작해서 안쪽으로 채우는 경우가 많고, 변형으로 중앙에서 시작해서 바깥쪽으로 나가는 방식도 있다  ❗좌측 상단에서 시작n, m = map(int, input().split(" "))graph = [[0 for _ in range(m)] for _ in range(n)]visited = [[0 for _ in range(m)] for _ in range(n)]dx = [0, 1, 0, -1]dy = [1, 0, -1, 0]d = 0x = 0y = 0graph[x][y] = 1visited[x][y] = 1for i in range(2, n * m+1): nx = x + dx[d]..

❗분할정복이란?문제를 작은 하위 문제로 나누고 각각의 하위 문제를 재귀적으로 해결한 뒤, 그 해답을 결합하여 원래 문제를 해결하는 방법이다. ❗분할정복 기본 원리 분할 (Divide):문제를 더 작은 하위 문제로 나눈다.문제를 동등한 크기의 여러 하위 문제로 분할한다.정복 (Conquer):각 하위 문제를 재귀적으로 해결한다.하위 문제들이 충분히 작아지면 재귀적으로 해결할 수 있으며 이를 기저 조건이라고 한다.기저 조건에서는 하위 문제를 더 이상 분할할 수 없는 상태에 도달한다.합병 (Combine):각각의 하위 문제에서 나온 해답을 합쳐 원래 문제의 해답을 구성한다. ❗예제result = "" # 현재 영역이 모두 같은 숫자로 이루어져 있는지 확인하는 함수def all_same(x, y, size):..

❗Recursion이란?함수가 자기 자신을 호출하는 프로그래밍 기법이다. 하나의 함수가 자신의 작업을 해결하는 과정에서 스스로를 다시 호출하여 문제를 반복적으로 해결하는 방식이다. 그래서 종종 복잡한 문제를 더 작은 문제로 나누어 해결할 때 사용한다. ❗ 재귀 함수의 구성 요소기본 조건 (Base Case)재귀 호출이 무한히 반복되지 않도록 하기 위한 종료 조건기본 조건이 만족되면 재귀 호출이 중단되고 함수가 결과를 반환하거나 종료됨재귀 호출 (Recursive Case)문제를 해결하기 위해 함수가 자기 자신을 호출하는 부분보통 이 과정에서 더 작은 크기의 문제로 재귀 호출이 이루어짐 ❗예제def factorial(n): if n == 1: return 1 return n * fa..

❗우선순위 큐(Priority Queue)란?일반적인 큐와 같은 성질을 가지고 있지만 삽입될 때 우선순위를 가지고 이에 따라 값이 처리되는 논리적 자료구조이다.  ❗구현 방법우선순위 큐는 배열, 연결 리스트, 힙(Heap) 등으로 구현할 수 있지만, 힙을 사용하는 것이 가장 일반적이다.힙은 최소힙과 최대힙으로 구분되며 최소 힙을 사용하면 우선순위가 낮은 값(최소값)이 루트에 위치하게 되어, O(log n)의 시간 복잡도로 우선순위가 가장 높은 요소를 추출할 수 있다.반대로 최대힙은 최댓값이 루트에 위치하게 된다.   ❗파이썬의 heapq파이썬에서는 heapq 라이브러리를 활용하여 우선순위 큐를 구현할 수 있다. ✏️import heapqfrom heapq import heapify, heappush, h..

❗BackTracking탐색 알고리즘 중 하나로 가능한 후보 해를 탐색하여 문제를 해결하는 방법이다.  ❗동작 방식1. 해를 구성하는 과정에서 해가 유망한지 확인유망하지 않은 경우 현재 경로를 포기하고 다른 경로로 이동한다.여기서 유망의 기준은 '현재 선택된 경로가 문제의 해답을 구하는 데에 있어서 가능성이 있다'는 의미이다.2. 유망한 경우, 해가 완전한지 확인완전한 해인 경우 해답을 출력하거나 저장한다.완전하지 않은 경우 다음 단계로 나아가 계속 해를 확장한다.  ❗파이썬 구현백트래킹 구현의 가장 대표적인 예시로 순열과 조합을 들 수 있다.이 두 알고리즘을 백트래킹으로 구현하기 위해선 뽑은 숫자를 저장한 arr 리스트, 방문 여부 파악을 위한 visited 리스트가 필요하며 백트래킹 함수 내부에선 해..

❗이분 탐색이분 탐색이란 정렬된 리스트 안에서 탐색 범위를 절반씩 줄여가며 원하는 값을 찾을 때까지 탐색하는 알고리즘이다 ❗동작 방식사전에 정렬된 리스트에서 39를 찾고자 한다. 1. start = 0, end = 9로 시작하여 두 값의 mid를 찾으면 인덱스 4가 된다.data[4]가 가리키는 값이 20이므로 39보단 작기 때문에 start의 위치는 인덱스 4보다 1 더 큰 곳으로 변경한다.2. start = 5, end = 9로 다시 탐색하면 mid는 인덱스 7이 된다.data[7]이 가리키는 값은 타켓인 39와 동일하기 때문에 탐색이 종료된다.이런 방식으로 target보다 현재 값이 작으면 start값을 변경하고, 크다면 end값을 변경한다. ❗파이썬 구현이분 탐색은 반복문과 재귀 2가지 방식으로 ..

❗BFS너비 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 연결된 자식 노드를 모두 탐색 후 다시 자식 노드가 부모 노드가 되어 이 부모 노드의 자식 노드를 넓게 탐색하는 방식이다BFS를 구현하는 방식으론 큐를 이용한다. ❗동작 방식위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.손으로 BFS를 풀 때는 1 -> 3 -> 2까지 탐색 후 다음 방문 노드는 3번 노드의 자식 노드인 6번과 4번이 된다.1 -> 3 -> 2 -> 6 -> 4 다음엔 2번 노드의 자식 노드인 5번을 방문하고1 -> 3 -> 2 -> 6 -> 4 -> 5 순서로 그래프 탐색을 완료할 수 있다. ❗파이썬 구현위의 케이스를 파이썬 코드로 구현한 것이다.graph = [[],[3,2],[3,1,4,5],[6,4..

❗DFS깊이 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 가장 깊숙히 들어가서 노드를 탐색한 후 다시 상위 노드로 이동하여 다른 루트를 탐색하는 방식이다.DFS를 구현하는 방식으론 스택과 재귀 호출이 있는데 해당 포스트에선 재귀 호출로 설명하고자 한다! ❗동작 방식위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.손으로 DFS를 풀 때는 1 -> 3 -> 6까지 탐색 후 더이상 나아갈 노드가 없기 때문에 3번 노드까지 거슬러 올라오게 된다.그 후 3번의 자식 노드 중 방문하지 않은 4를 방문하고 이어서 탐색하면결국 DFS의 방문 노드 순서는 1 -> 3 -> 6 -> 4 -> 2 -> 5이 된다. ❗파이썬 구현위의 케이스를 파이썬 코드로 구현한 것이다.graph = [[],[3,2..