유니온 - 파인드 알고리즘 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조 - 집합을 구현하는데 트리구조를 이용하여 구현 - 여러 노드가 존재할때 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 - find : x가 어떤 집합에 포함되어있는지 찾는 연산, 집합의 루트 노드경로를 짧게 압축 시킴 - Union : x와 y가 포함되어 있는 집합을 합치는 연산 동작 방법 1. union 연산 확인 : 서로 연결된 두 노드를 확인 1-1. A의 루트 노드 A'와 B루트노드 B'를 찾는다(find) 2-2. A'를 B'의 부모 노드로 설정 2. 모든 연산을 처리할때까지 1번 반..

레드블랙트리 (RED-Black Tree) 자가균형 이진탐색트리로써, 대표적으로 연관배열 등을 구현하는데 쓰이는 자료구조 - 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고 최악의 경우에도 우수한 실행시간을 보장 - 이진트리의 구조를 그대로 채용하되, 딱 하나 색상(Color)라는 속성을 노드에 추가함으로서 자동으로 균형을 유지 - 이진 검색트리의 모든 노드에 성질에 따라 레드 또는 블랙의 색상 특성 - 노드는 레드 또는 블랙의 색을 가짐 - 루트노드는 빨간노드일 수 없음 (검정으로 변환) - 모든 리프노드는 블랙 (NIL 노드는 모두 블랙) - 빨간노드는 두 개의 검정 노드를 가짐 (자식이 없을 경우 블랙 NIL 노드를 가짐) - 루트에서 리프로 가는 경로의 검정 노드의 수는 모두 같음..

2018 KAKAO BLIND RECRUITMENT (2018 카카오 블라인드 채용 문제) 캐시 크기가 주어질때 해당 도시들을 검색할 때 실행 시간을 구하는 문제입니다. 캐시 교체 알고리즘은 LRU를 사용합니다. *LRU (Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법 4번째 예제의 경우 (cache miss) 1. 캐시 : Jeju 실행시간 : 5초 (cache miss) 2. 캐시 : Pangyo, Jeju 실행시간 : 10초 (cache miss) 3. 캐시 : Seoul, Pangyo, Jeju 실행시간 : 15초 (cache miss) 4. 캐시 : NewYork, Seoul, Pangyo, Jeju 실행시간 : 20초 (cache miss) 5. ..

2019 KAKAO BLIND RECRUITMENT (2019 카카오 블라인드 채용 문제) 블록 게임을 통해 총 몇개의 블록이 제거되는지 찾는 문제입니다. 문제 1. 2*2 블럭의 모양이 모두 같으면 해당 2*2 블럭은 제거됩니다. 2. 1.번을 통해 블럭들이 제거되면 블럭들 아래에 블럭이 없는 경우 블럭을 내립니다. 3. 1, 2번을 더 이상 할 수 없을때 까지 반복한 후 제거된 블럭 개수를 출력합니다. 해결 방법 1. temp = board (temp는 제거될 블럭들을 임시적으로 표시하는 용도) 2. 반복문을 통해 2*2 모양이 같은 블럭 탐색 2-1. 같은 경우 temp에 해당 블럭들 체크 (' ' 공백으로 처리) 2-2. check 변수를 true 변경 (블럭 제거 과정이 있었다는 것을 의미) 3..

2018 KAKAO BLIND RECRUITMENT (2018 카카오 블라인드 채용 문제) 두개의 문자열을 '자카드 유사도' 방법을 통해서 유사도를 찾는 문제입니다. 문제 해결 방법 1. 입력 받은 문자열을 소문자로 변경 2. 문자열을 2글자씩 끊어서 저장 (특수문자가 포함된 경우 패스) (s1, s2라고 지칭) 3. 2.에서 저장된 문자열들(s1, s2)끼리 비교 (같은게 있을 경우 카운팅(count), 체크 = 중복 체크 제거) 4. 합집합 = s1.size + s2.size - count, 교집합 = count 유사도 = count / (s1.size() + s2.size() - count) * 65536; 코드 #include #include #include using namespace std; ..

브루트 포스 알고리즘 (brute force) 완전탐색 알고리즘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과를 가져오는 알고리즘 - 구현이 쉬운 편 - 시간적으로 매우 비효율적 - 알고리즘은 항상 최적해를 구할 수 있음 활용 - 선형구조: 순차탐색 - 비선형구조: 백트래킹(backTracking), 맹목적 탐색(BFS, DFS) 백트래킹 (Backtracing) 알고리즘 되추적이라는 뜻으로 이전 단계로 거슬러 올라가 다른 가능성을 찾아보는 방법 모든 가능성을 찾아보는 것은 맞지만 그중에서도 가능성이 있는 것만 찾는 가지치기(Pruning) 기법을 사용 *가지치기 : 조건을 맞출 수 없는 경우, 해당 경우를 제외 시키는 방법 브루트포스, 백트래킹, DFS 차이 브루트 포스 알고리즘 =..

벨만 포드 (Bellman-Ford) 알고리즘 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘 - 최단 경로를 찾는 알고리즘 (다익스트라, 벨만 포드, 플로이드 와샬) - 가중치가 음수 일 때도 사용이 가능 - 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우 다익스트라 알고리즘을 사용 - 경로 중에 음수 사이클이 존재하는 경우 확인 가능 음수 사이클 확인 방법 그래프의 정점의 개수를 V라고 할 때, 인접 간선을 검사하고 거리 값을 갱신하는 과정은 V - 1번이 필요 음수 사이클을 확인하기 위해 V - 1번 대신 V번 검사를 하고 V번째에 값이 갱신 되었을 경우, 음수 사이클이 존재 벨만-포드 알고리즘 프로세스 1. 시작 정점을 결정 2. 시작 정점부터 다른 정점까지 거리 값 모두 무..

분할 정복 알고리즘 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 개념 - 대표적으로 퀵소트, 병합정렬이 있음 - 문제를 둘 이상의 부분 분제로 나누는 자연스러운 방법이 있어야 함 - 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 함 분할: 문제를 동일한 유형의 여러 하위 문제로 나눔 정복: 가장 작은 단위의 하위 문제를 해결하여 정복 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합 장점 - 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점을 가짐 - 같은 작업을 더 빠르게 처리가 가능 단점 - 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 ..