반응형 Develop/Coding Test | Algorithm25 이진 트리 트리(Tree) 는 방향이 존재하는 그래프의 일종으로 부모 정점 밑에 여러 자식 정점이 연결되고, 자식 정점 각각에 다시 자식 정점이 연결되는 재귀적 형태의 자료구조입니다. 그 중에서 각 정점이 최대 2개의 자식 정점을 가지는 트리를 이진 트리(Binary Tree) 라고 합니다.종류정점이 채워져 있는 형태에 따라서 대표적으로 포화 이진 트리, 완전 이진 트리, 편향 이진 트리가 존재합니다.포화 이진 트리마지막 레벨까지 모든 정점이 채워져 있는 경우, 포화 이진 트리라고 부릅니다. 1 --- level 1 / \\\\ 2 3 --- level 2 / \\\\ / \\\\ 4 5 6 7 .. 2025. 8. 11. 퀵 정렬 (Quick Sort)의 기본 개념과 동작 원리 1. 퀵 정렬이란? 왜 필요한가?퀵 정렬(Quick Sort) 은 이름에서 알 수 있듯 매우 빠른 정렬 속도를 자랑하는 알고리즘입니다. '분할 정복(Divide and Conquer)'이라는 전략을 사용하여 전체 리스트를 더 작은 단위로 나누어 정렬합니다.왜 필요할까요? 수많은 정렬 알고리즘 중 퀵 정렬이 널리 사랑받는 이유는 평균적인 상황에서 최고의 성능을 보이기 때문입니다. 특히, 정렬해야 할 데이터의 양이 많을 때 그 진가가 드러납니다. 대부분의 프로그래밍 언어에서 표준 정렬 라이브러리의 일부로 채택될 만큼 효율성과 범용성이 뛰어납니다.java.util.Arrays.sort() (primitive types): Java의 Arrays.sort() 메서드는 듀얼 피벗 퀵 정렬(Dual-Pivot Qu.. 2025. 7. 23. 트라이(Trie) 자료구조 트라이(Trie) 는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조입니다. 트라이는 문자열을 탐색할 때 단순히 비교하는 것에 비해서 효율적으로 찾을 수 있지만, 각 정점이 자식에 대한 링크를 모두 가지고 있기 때문에 저장 공간을 더욱 많이 사용한다는 특징이 있습니다. 주로, 검색어 자동완성이나 사전 찾기 기능을 구현할 때 트라이 자료구조를 고려할 수 있습니다.출처 : 위키백과구현 방법트라이 자료구조에서 루트는 항상 비어있으며, 각 간선은 추가될 문자를 키로 가지고 있습니다. 또한, 각 정점은 이전 정점의 값과 간선의 키를 더한 결과를 값으로 가집니다. 트라이를 구현할 때는 이러한 구조를 염두에 두면서 해시 테이블과 연결 리스트를 이용하여 구현할 수 있습니다.class Trie.. 2025. 7. 18. 선택 정렬 (Selection Sort) 배열의 모든 요소를 하나씩 확인하면서, 현재 위치에 와야 할 가장 작은(혹은 가장 큰) 요소를 찾아 그 위치에 배치하는 방식입니다.1. 동작 방식선택 정렬은 다음과 같은 단계를 반복하여 정렬을 수행합니다.최소값(또는 최대값) 찾기: 배열의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 찾습니다.위치 교환: 찾아낸 최소값(또는 최대값)을 정렬되지 않은 부분의 첫 번째 요소와 교환합니다.반복: 위 과정을 정렬되지 않은 다음 부분을 대상으로 반복합니다. 배열 전체가 정렬될 때까지 이 과정을 계속합니다.2. 예제선택 정렬 이용 오름차순으로 정렬하는 과정 설명 초기 배열: [64, 25, 12, 22, 11]1단계: 첫 번째 요소(인덱스 0) 위치 결정정렬되지 않은 부분: [64, 25, 12, 22,.. 2025. 7. 9. [BOJ] 15657번: N과 M (8) https://www.acmicpc.net/problem/15657* 백트래킹: "경로를 탐색하다가 해가 될 가능성이 없으면 즉시 되돌아가 다른 경로를 탐색하는" 알고리즘문제 정리N개의 자연수 중에서 M개를 고른 수열: N개의 주어진 숫자들 중에서 M개를 선택하여 수열을 만듭니다.같은 수를 여러 번 골라도 된다: 중복 선택이 허용됩니다.고른 수열은 비내림차순이어야 한다: A1≤A2≤⋯≤AM 와 같이, 뒤에 오는 숫자는 앞에 오는 숫자보다 작으면 안 됩니다.수열은 사전 순으로 증가하는 순서로 출력: 최종 결과도 사전 순으로 정렬되어야 합니다. (이 조건은 입력으로 주어진 N개의 수를 미리 정렬하고, DFS 탐색 시 올바른 순서로 탐색하면 자동으로 만족됩니다.)백트래킹의 적용 원리백트래킹은 "경로를 탐.. 2025. 6. 11. 연결 리스트 연결 리스트(Linked List) 는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있는데요. 이때, 첫 번째 노드를 HEAD, 마지막 노드를 TAIL 이라고 합니다. 연결 리스트는 메모리가 허용하는 한 요소를 계속 삽입할 수 있으며, 시각 복잡도는 탐색에는 O(n), 노드 삽입과 삭제는 O(1)라는 특징을 가지고 있습니다. 해당 아이디어로 파생된 자료구조는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List, Circular Linked List)가 존재합니다.배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용합니다. 반면, 연결 리스트는 메모.. 2025. 5. 30. DFS BFS 프루닝 기법 DFS/BFS에서 프루닝 기법이란? - 문제 예시와 실전 코드 포함프루닝(Pruning) 기법탐색 도중 불필요하거나 정답이 될 수 없는 경로를 미리 차단함으로써 탐색 시간을 줄이는 전략일반적인 프루닝 전략에는 다음이 포함됩니다:조건을 만족하지 않으면 더 이상 탐색하지 않기이미 더 나은 정답이 나온 상태라면 더 탐색하지 않기방문한 노드를 다시 방문하지 않기결과가 항상 나빠지는 경로 제거효과탐색 경로 수 감소: 중복되거나 더 비싼 경로는 무시시간 복잡도 개선: 큐에 들어가는 노드 수 감소결과의 신뢰성 유지: 정답에 영향을 주지 않으면서 성능 향상전략 설명DFS 프루닝재귀호출 전에 조건 체크하여 불필요한 경로 차단BFS 프루닝큐에 넣기 전에 최단 비용 조건 확인공통 장점탐색 공간을 줄여 속도 개선예제: 최소 .. 2025. 5. 22. 벨만-포드 알고리즘 그래프 최단 경로 구하기 2. 벨만-포드 알고리즘 최단 경로는 '가중치' 유무에 따라 다르다가중치가 없는 그래프에서는 간선 개수가 가장 적은 경로가중치가 있는 그래프에서는 가중치의 총합이 최소가 되는 경로벨만-포드 알고리즘노드에서 노드까지의 최소 비용을 구한다.매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로, '음의 가중치'를 가지는 그래프에서도 최단 경로를 구할 수 있는 특징이 있다.다익스트라 알고리즘은 음의 가중치를 허용하지 않는다는 점과 차별화된다.시작 노드 최소 비용:0, 나머지 노드 INF 초기화 (최소 비용을 갱신할 때 직전 노드 갱신)노드 개수 -1 만큼 연산 반복최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신하고, 직전 노드 값도 같이 갱신한다.마지막에 과정.. 2025. 4. 25. 유니온-파인드 알고리즘 집합 알고리즘에 주로 사용되는 연산: 합치기, 탐색Union: 합치기, Find: 탐색활용 시나리오조건: 여러 개의 그룹이 형성되어 있음문제: 특정 원소가 주어졌을 때, 이 원소들이 같은 그룹인지 판단해야 할 경우유니온-파인드 알고리즘과 경로 압축 알고리즘 활용파인드 연산특정 노드의 루트 노드가 무엇인지 탐색하는 방법특정 노드가 같은 집합에 있는지 확인할 때 사용A, B 두 노드가 있을 때 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것특정 노드부터 재귀로 거슬러 올라가며 루트 노드를 찾음과정현재 노드의 부모 노드를 확인한다. 부모 노드를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료한다.1에서 찾기 연산이 종료되지 않으면 1을 반복한다.1단계집합을 정의하고, 노드 7의 루트 노드를 찾.. 2025. 4. 4. 이전 1 2 3 다음 728x90 반응형
