Carat Thinker

트리 자료구조에 대한 설명은 아래 포스팅을 참고해주세요 https://lifeofsw.tistory.com/36 자료구조 ⑤ 트리(+ 백준 1068번) 트리의 정의 및 특징 트리 : 노드와 에지로 연결된 그래프의 특수한 형태 그래프의 표현으로도 tree를 표현할 수 있다 특징 순환 구조를 가지지 않고 1개의 루트 노드가 존재한다 루트 노드를 제 lifeofsw.tistory.com 트라이 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조 단어를 사전의 형태로 생성한 뒤, 트리의 부모-자식 노드 관계를 이용하여 검색 특징 N진 트리 : 문자 종류의 개수에 따라 N이 결정된다 알파벳 : 26개 글자로 구성되어 있으므로 26진 트리 루트 노드 : 빈 문자열을 뜻하는 공백 상태 백준 14425..

오늘은 그래프 알고리즘에 대해서 포스팅하려고 합니다. 그래프 자료구조에 대한 설명은 첨부된 링크를 참고해주세요! https://lifeofsw.tistory.com/26 자료구조 ④ 그래프 : 정의, 표현 방법 그래프란 노드와 에지로 구성된 집합 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결하는 요소 위 그림은 방향이 있는 그래프이다. 그래프는 방향이 없을 수도 있으며, 양방향 그래프일수도 lifeofsw.tistory.com 유니온 파인드 여러 영역에서 사용되는 알고리즘 그래프의 사이클이 생성되는지 판별하는 알고리즘 union 연산 : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 노드 a, b,가 $ a \in A, b \in B $ 일 때, union(a, b) = $..

유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘으로, 코딩 테스트에서는 재귀 형태로 구현된다 과정 큰 수를 작은 수로 나누는 MOD 연산을 수행한다 MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)로 MOD 연산을 수행한다 앞 단계를 반복하다가 나머지가 0이 되는 순간의 작은 수 = 최대 공약수 최소 공배수도 구할 수 있다 최소 공배수 = a * b / 최대 공약수 확장 유클리드 호제법 : 방정식의 해 구하기 방정식 : ax + by = c 단 a,b,x,y,c는 정수 c는 최대 공약수 gcd(a,b)의 배수 백준 9613번 풀이(python) 과정 input 재정의 및 t 입력받기 GCD 함수 구현 나머지가 0이면 작은 수 출력 나머지가 0..

소수 구하기 : 에라토스테네스의 체 소수 : 1과 자기 자신 외에 약수가 존재하지 않는 수 에라토스테네스의 체 이중 반복문을 사용 : 시간복잡도 $ O(N^2) $ 단 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하므로 $ O(Nlog(logN)) $ 과정 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우, 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하며 지운다 특정 숫자의 배수는 소수가 아니므로 지운다 2부터 시작하는 이유 : 1은 소수가 아니므로 & 1은 모든 수의 약수이므로 처음으로 선택된 숫자는 지우지 않는다 : 배수가 아닌 처음으로 선택된 숫자는 소수이므로 리스트의 끝까지 2를 반복한 후, 리스트에서 남아있는 모든 ..

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 특징 : 최적의 해를 보장하지 않음 과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 해 검사 : 현재까지 선택한 해가 전체 문제를 해결할 수 있는지 검사 전체 문제를 해결하지 못한다면 반복 백준 2805번(python) 프로세스 input 재정의 N, M, 나무 높이 입력 받기 나무 높이 정렬하기 시작점 = 1, 끝점 = 나무의 최대값 시작점이 끝점보다 커질 때까지 반복 벌목된 나무의 총합 0으로 초기화 중앙값의 인덱스 저장 저장된 나무들의 높이에 대해 반복 나무가 절단 길이보다 길다면 벌목된 나무의 총합에 (..

깊이 우선 탐색(Depth First Search, DFS) 그래프 완전 탐색 기법으로, 모든 노드를 탐색한다 탐색할 한쪽 분기를 정함 → 최대 깊이까지 탐색 → 다른 분기로 이동 → 반복 아래 사진의 경우, 1 → 2 → 5 → 8을 먼저 탐색하고 2 → 4를 탐색한다. 이후 다른 분기로 이동하여 1 → 3 → 6을 탐색하고 3 → 7을 탐색한다 특징 재귀 함수로 구현한다 스택 자료 구조 이용 : 후입선출 시간복잡도 : O(노드 수 + 엣지 수) 그래프 인접 리스트로 표현 주의할 점 스택오버플로우 : 일정 수준 이상으로 들어가는 것 한 번 방문한 노드를 다시 방문하면 안 된다 : 노드 방문 여부를 체크할 리스트 필요 방문 리스트에 포함되어 있는 노드는 재삽입하지 않는 것이 핵심 단계 인접 리스트로 그래..

정렬에는 병합 정렬 외에도 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 기수 정렬 등이 있지만 시간복잡도가 좋지 않아서 잘 사용되지 않습니다. 오늘은 시간복잡도가 nlogn으로 낮은 편인 병합 정렬에 대해서만 다루겠습니다 병합 정렬 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 분할 정복 방식 분할한 집합을 정렬하며 합친다 2개의 그룹을 병합하는 과정을 이해하는 것이 중요하다 투포인터를 사용한다 과정 데이터를 분할한다 포인터를 세트의 같은 인덱스에 위치시킨다 왼쪽 포인터와 오른쪽 포인터를 비교하여 작은 값을 결과 배열에 추가한다 포인터를 오른쪽으로 1칸 이동시킨다 한쪽 세트의 모든 데이터를 입력했다면 남은 세트의 데이터는 마지막에 배치한다 swap 횟수를 계산하는 응용 문제 등으로..

스택 가장 마지막에 삽입된 data가 가장 먼저 나오는 구조 후입선출 구조 : Last in, First out 삽입과 삭제가 한쪽에서만 일어난다 재귀함수 알고리즘 원리와 일맥상통 삽입 및 삭제 위치 : top 연산 append : 데이터 삽입 pop : 데이터를 삭제하고 삭제되는 데이터 출력 s[-1] : top 위치에 있는 데이터를 단순 확인 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩 테스트에 효과적 백준 10828번 풀이(python) 프로세스 명령 개수 입력 받기 : input 재정의할 것 리스트로 스택 구현 반복문을 통해 명령 입력 받기 입력받은 명령을 명령과 데이터로 분할하기 명령에 따라서 데이터 처리하기 숫자 출력 시 print를 사용하지 않으면 오답으로 처리된다 코드 import sys..

투 포인터 2개의 포인터로 점의 위치를 기록하며 처리하는 알고리즘 과정 시작점과 끝점 = 0번째 인덱스 현재 부분합이 N과 같다면 count +1 현재 부분합이 N보다 작다면 end +1 부분합을 크게 하기 위해서 종료점 이동 현재 부분합이 N보다 크다면 start +1 부분합을 작게 하기 위해서 시작점 이동 2 ~ 4를 반복하며 모든 경우를 확인 백준 1940번 풀이(python) 프로세스 숫자 입력받기 입력받은 숫자를 정렬한다 시작점은 0으로, 끝점은 N-1로 초기화 갑옷의 개수인 count는 0으로 초기화 시작점과 끝점이 같아질 때까지 반복문 수행 시작점과 끝점을 더한 값이 M보다 작다면 시작 위치를 오른쪽으로 이동 시작점과 끝점을 더한 값이 M보다 크다면 끝점 위치를 왼쪽으로 이동 시작점과 끝점을..

배열과 리스트 파이썬에서는 둘을 구분하지 않는다 파이썬의 배열(리스트) 특징 인덱스를 이용하여 바로 접근 가능 가변적인 길이 배열 리스트 인덱스O: 배열의 값에 바로 접근 가능 인덱스X: 접근 속도가 느리다 연속적인 형태 : 삽입, 삭제 속도 느림 포인터로 연결되어 있음 : 삽입, 삭제 속도 빠름 고정된 크기 가변적인 크기 백준 1546번 풀이(python) 프로세스 과목 개수, 시험 성적 입력 받기 최대값 구하기 총합 구하기 : 점수를 일일히 수정하지 않고 총합을 수정해야 시간복잡도를 줄일 수 있다 점수를 일일히 수정하는 방향으로 코드를 짜면 틀린다. 오차 조건때문인듯? 점수 수정하기 : 전체를 최대값으로 나눈 다음, 과목 개수로 나누고 100을 곱한다 코드 n = input() #과목 개수 numbe..