본문 바로가기

전체 글92

그래프 탐색 알고리즘, DFS(Depth-First Search) DFS(깊이 우선 탐색)특정 방향으로 최대한 깊이 들어가서 빠져나오는 방식DFS는 스택 자료구조 사용스택(Stack): 먼저 들어온 데이터가 나중에 나가는 형식 → FILODFS는 2차원 배열(리스트)로 그래프 표현그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법으로, 완전탐색 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나인접 리스트 표현 방식0 12, 321, 531, 4, 543, 552, 3, 4 기본 동작 방식시작 노드를 스택에 넣고 [방문 처리]스택에 마지막으로 들어온 노드에 방문하지 않은 인접 노드가 있는지 확인• 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 [방문 처리]• 없다면, 현재 노드(스택에 마지막으로 들어온 노드)를 스택에서 추출2번 과정을 .. 2026. 4. 4.

백트래킹 모든 경우의 수 고려할 때 사용일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용DFS와의 차이점DFS는 일반적으로 완전 탐색 목적으로, 재귀 함수를 이용해 구현백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 단순히 완전 탐색하는 것이 아니라 조건에 따라 유망한 노드로 이동그래프 표현 방식(2가지)1. 인접행렬0100101101010110 2. 인접리스트0 1221, 3, 432, 442, 3 백트래킹 기본 형태function recursive() { if 종료 조건을 만족한다면 { 처리; } for 자식 노드를 하나씩 확인하며 { if 임의의 조건을 만족한다면 { 자식 노드 방문 처리; 재귀 함수 호출; .. 2026. 4. 4.

이진탐색 순차 탐색 vs 이진 탐색ex) 리스트에서 12인 원소의 위치 찾기순차 탐색리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인 → 시간복잡도: O(N)이진 탐색정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색 → 시간복잡도: O(logN)이진탐색 수행할 때 시작점(left)와 끝점(end)을 기준으로 탐색 범위 명시각 단계마다 탐색 범위를 2로 나누기이상적인 경우 매 단계마다 범위가 반으로 감소 → log 복잡도를 가짐대표적인 사례매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우이진 탐색 코드이진 탐색은 배열이 정렬되어있다는 가정하에 수행1. 재귀함수 이용function binarySea.. 2026. 4. 4.

그리디(Greedy)/탐욕적 알고리즘 그리디 알고리즘현재 상황에서 당장 가장 좋아보이는 상황만을 선택하는 알고리즘최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많음 → 최적의 해에 가장 가까운 근사 해를 구할 수 있음ex) 루트에서 출발해서 단말 노드까지 가는 경우, 거쳐가는 노드의 합이 가장 큰 경우 구하기완전탐색으로 풀기최적의 해: 10 (1→4→5)모든 상황을 고려해야 함그리디 알고리즘으로 풀기매 상황에서 단순히 가장 큰 노드를 선택: 8 (1→5→2)모든 경우의 수를 고려하지 않아도 되지만, 최적의 해는 아니다![접근 방식]1. 방법 고안하기: 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안2. 정당성 확인하기: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인(증명 단계) ex) 거스름돈 문제카운터에 500원, .. 2026. 4. 4.

이전 1 ··· 6 7 8 9 10 11 12 ··· 23 다음

티스토리툴바