kjp0411 님의 블로그

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.기능특징시간 복잡도(노드 수: V, 엣지 수: E)노드 간의 순서를 결정사이클이 없어야 함O(V + E) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다.또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없습니다. 위상 정렬의 핵심 이론위상 정렬의 원리 이해하기1. 진입 차수는 자기 자신을 가리키는 엣지의 개수입니다.

유니온 파인드일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연겨해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘 유니온 파인드의 핵심 이론union, find 연산union 연산: 각 노드가 속한 집합을 1개로 합치는 연산입니다.find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산입니다.유니온 파인드의 원리 이해하기1. 유니온 파인드를 표현하는 방법은 1차원 리스트를 이용하는 것입니다.처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드이므로 리스트를 자신의 인덱스 값으로 초기화 합니다. 2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행합니다. 3. ..

그래프는 노드와 엣지로 구성된 집합입니다.노드는 데이터를 표현하는 단위이고 엣지는 노드를 연결합니다.

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘입니다.일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만유클리드 호제법은 좀 더 간단합니다. 유클리드 호제법의 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 합니다.MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문입니다.연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 → 10 % 4 = 2 MOD 연산으로 구현하는 유클리드 호제법큰 수를 작은 수로 나누는 MOD 연산을 수행한다.앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.단계 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 ..

수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻합니다.실제 코딩 테스트에서는 모든 정수론의 분야가 나오지 않습니다.따라서 정수론 영역에서 가장 많이 등장하는 소수 부분과 호제법 부분을 정리하겠습니다. 소수소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수입니다.즉, 1과 자기 자신 외에 약수가 존재하지 않는 수를 의미합니다. 소수 구하기의 핵심 이론소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있습니다. 에라토스테네스의 체 원리구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.2부터 시작해서 현재 선택한 숫자가 지워지지 않는 숫자라면 해당 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택한 숫자는 지우지 않는다...

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다. 그리디 알고리즘의 수행 과정1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.(전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.)

이진 탐색데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다.대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘입니다.기능특징시간 복잡도타깃 데이터 검색중앙값 비교를 이용한 대상 축소 방식O(logN) 이진 탐색의 핵심 이론이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복합니다.※ 내림차순이라면 조건을 반대로 하여 과정을 반복하면 됩니다. 이진 탐색 과정현재 데이터셋의 중앙값을 선택합니다.중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택합니다.중앙값 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료합니다. 이렇게 이진..

너비 우선 탐색(BFS)너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나입니다.그래프의 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다.탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다.기능특징시간 복잡도(노드 수: V, 엣지 수: E)그래프 완전 탐색FIFO 탐색Queue 자료구조 이용O(V + E) 너비 우선 탐색의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 리스트가 필요합니다.그래프를 인접 리스트로 표현하..

탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 의미합니다.주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요합니다. 깊이 우선 탐색(DFS)그래프의 완전 탐색 기법 중 하나입니다.그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘기능특징시간 복잡도(노드 수: V, 엣지 수: E)그래프 완전 탐색재귀 함수로 구현스택 자료구조 이용O(V + E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 합니다.깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있습니..