이니의 공부일지

백트래킹이란? 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 올라가는(방금 왔던 길을 되짚어가는) 알고리즘 백트래킹과 DFS의 차이 백트래킹 불필요한 탐색을 하지 않는다. DFS 모든 경우의 수를 탐색한다. 백트래킹 구현 완전탐색 기법인 BFS 와 DFS 로 모두 구현 가능 백트래킹의 특성(전 단계로 다시 올라가는) 때문에 DFS의 구현이 더 편하다. 한정 조건 이 가장 중요하다. 모든 경우의 수에서 한정 조건 을 만족하는 경우를 탐색 대표 문제 15649번: N과 M (1) 문제 자연수 N과 M이 주어질 때, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하자 💡 고려 사항 배열의 길이가 M을 넘지 ..

냅색 알고리즘이란? 한 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 냅색 알고리즘을 나누는 기준 담을 수 있는 물건이 나뉠 수 있는가, 없는가? 담을 수 있는 물건이 나누어 질 때 분할가능 배낭문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 수 없을 때 0-1 배낭 문제(0-1 Knapsack Problem) 냅색 알고리즘 예시 가방에 20kg까지 담을 수 있습니다. 현재 3가지 물건을 가지고 있을 때, 가치를 최대로 가지려면 어떤 물건들을 담아야 하나요? A : 가치 10, 무게 14kg B : 가치 7, 무게 10kg C : 가치 8, 무게 10kg..

DFS 일반적으로 재귀를 사용하여 구현한다. BFS 큐를 사용하여 구현한다. BFS는 정의상 시작점으로부터 가까운 지점부터 방문하게 되기 때문에 그림에서처럼 가중치가 전부 동일한 그래프에서는 최단거리를 확실하게 구해줄 수 있는 것이다. BFS를 이용한 최단거리는, 가중치만 전부 동일하다면 방향 그래프에서도 동일하게 적용된다.

트리의 정의는 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프이다. 트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징이다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부른다. 그 외에도 추가적인 용어들은 다음과 같다. 노드: 각 지점을 의미합니다. 정점이라 부르기도 한다. 간선: 두 노드를 연결하는 선을 의미합니다. 에지라고 부르기도 한다. 루트 노드: 트리에서 맨 꼭대기를 의미한다. 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 부른다. 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미한다. 깊이: 루트 노드와..

스택 ( stack ) 스택은 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 말한다. 즉, 맨 아래에 있는 데이터를 꺼내기 위해서는 그 위의 데이터를 모두 꺼내야 할 것이다. 이런 구조를 후입선출 구조(LIFO; Last In First Out)라고 부른다. stack은 크게 5가지 함수 사용이 가능하다. 1. push(x) # x를 stack의 맨 위에 올려 놓는다. 2. size() # stack 위에 쌓인 블럭의 개수를 반환한다. 3. empty() # stack 위가 비어있다면 true, 비어있지 않다면 false를 반환한다. 4. top() # stack의 맨 위에 있는 숫자 값을 반환한다. 단, stack에서 그 블럭을 제거하지는 않는다. 5. pop() # stack의 맨 위에 있는..

이진탐색 이진탐색은, 찾아야하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것이다. 이진탐색을 사용하는 이유는 순차탐색보다 더 빠르기 때문이다. 실제 이진탐색의 시간복잡도는 O(logN)이다. 루프를 한 번 돌때 마다, 우리가 다루는 구간의 길이는 반으로 감소하고, 구간의 길이가 1이 될 때 까지 계속 반복해서 탐색하는 것을 볼 수 있다. 즉, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN)이 되는 것을 볼 수 있다. O(N)과 O(logN)은 정말 큰 차이를 보인다. 만약, N이 4,294,967,296이라면, O(logN)의 시간복잡도를..

버블 정렬(거품 정렬) 거품 정렬은 가장 단순한 정렬 알고리즘이다. 아이디어는 다음과 같다. 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해준다. 이런 절차를 정렬이 될 때 까지 반복한다. 코드를 작성하는 것은 어렵지 않지만, 상당히 비효율적인 알고리즘이기 때문에 성능이 다른 알고리즘에 비해 좋지 않다는 단점이 있다. 버블 정렬의 시간복잡도는 O(N2) 이다. 버블 정렬을 구현한 코드는 다음과 같다. n = int(input()) m = list(map(int, input().split())) for i in range(n): cnt = 0 for j in range(1, n): if m[j] >..

보호되어 있는 글입니다.

인덴트(들여쓰기) python의 대표적인 특징으로써 공백 4칸을 원칙으로 한다. 네이밍 컨벤션 python의 변수명 네이밍 컨벤션은 자바와 달리, 각 언어를 밑줄( _ )로 구분하여 표기하는 스네이크 케이스를 따른다. (스네이크 케이스는 일반적으로 모두 소문자로 표기하지만, 경우에 따라 시작 문자는 대문자로도 표기한다.) 타입 힌트 python은 동적 타이핑 언어이지만, 타입을 지정할 수 있는 타입 힌트 기능이 존재한다. ex) def fn(a: int) -> bool: 하지만, 동적으로 할당될 수 있으므로, 문자열에 정수를 할당하는 등의 사용은 지양해야 한다. 리스트 컴프리헨션 python은 map, filter와 같은 함수형 기능을 지원하며, 람다 표현식도 지원한다. ex) >>> list(map(l..

DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 제한 조건 시간 제한 : 2초 메모리 제한 : 128MB 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS..