본문 바로가기

코딩테스트/이코테8

8. 기타 그래프 이론 안녕하세요. 😊 오늘은 기타 그래프 이론에 대해 정리해보려고 합니다. 서로소 집합 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조 라고 불리기도 한다. 여러 개의 합치진 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 .. 2023. 11. 17.
7. 최단 경로 알고리즘 안녕하세요. 😊 오늘은 최단 경로 알고리즘 에 대해 정리해보려고 합니다. 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드 에서 출발하여 다른 모든 노드 로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨 매 상황에서 가장 비용이 적은.. 2023. 11. 16.
6.다이나믹 프로그래밍 안녕하세요. 😊 오늘은 다이나믹 프로그래밍 에 대해 정리해보려고 합니다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. 다이나믹 프로그래밍은 통계 계획법이라고도 불립니다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 을 의미합니다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사.. 2023. 11. 13.
5. 이진 탐색 알고리즘 안녕하세요. 😊 오늘은 이진 탐색 알고리즘에 대해 정리해보려고 합니다. 이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N에 비례 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다. 2단계를 거치면 8개 가량의 데이터만 남는다. 3단계를 거치면 4개 가량의 데이터만 남는다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는.. 2023. 11. 12.
4. 정렬 알고리즘 안녕하세요. 😊 오늘은 정렬 알고리즘에 대해 정리해보려고 합니다. 정렬 알고리즘 정렬(Sorting) 이란 데이터를 특정한 기준에 따라 순서대로 나열한 것 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것 반복 선택 정렬 소스코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)) : min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)) : if array[min_index] > array[j] : min_index = j array[i], array[min_index] = array[min_index], array[i] # 스와.. 2023. 11. 9.
3. DFS & BFS 알고리즘 안녕하세요. 😊 오늘은 DFS & BFS 알고리즘에 대해 정리해보려고 합니다. 그래프 탐색 알고리즘 DFS / BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 DFS/BFS는 코딩 테스트에서 자주 등장하는 유형 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택 시각화 할 수 있음 스택 구현 예제 stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() # 7 삭제 stack.append(1) stack... 2023. 11. 5.

티스토리툴바