본문 바로가기

inistory

Visits

Today

Yesterday

Recent Posts

Popular Posts

Recent Comments

Algorithm/알고리즘

Algorithm/알고리즘 [Algorithm] 투 포인터 알고리즘 (Two Pointers) 1. 투 포인터(Two Pointers) 알고리즘 배열의 특정 연속된 구간을 처리하는 경우 사용 리스트에 순차적으로 접근해야 할 때, 두개의 점을 이용해 위치를 기록하면서 처리하는 기법 $O(N)$ 2. 예시 문제 [1,2,3,2,5] 합이 5 인 부분 연속 수열의 개수 구하시오 각 지점에서 구간을 늘려가며 연속되는 수를 확인하는 방법? 시간 복잡도 : $O(n^2)$ 데이터의 개수가 많아지면 시간이 많이 걸림 $O(N)$으로 풀려면? 투 포인터 알고리즘 사용하기 3. 풀이 start, end 포인터를 첫 번째 인덱스를 가리키도록! 합이 5보다 작으면 end 오른쪽으로 이동 (합을 늘림) 합이 5보다 크면 start를 오른쪽으로 이동 (합을 줄임) 합이 5가되면 count, start를 오른쪽으로 이동 ..

[Algorithm] DFS & BFS

Algorithm/알고리즘 [Algorithm] DFS & BFS DFS( Depth-First Search) 깊이우선탐색(DFS) : 스택 자료구조(혹은 재귀함수)를 이용, 깊은 부분을 우선적으로 탐색하는 알고리즘 탐색 시작 노드를 스택에 갑입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않는 입접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS, BFS 둘 다 시간 복잡도는 같다 실제로는 스택영역(혹은 재귀함수)를 사용하지 않는 BFS(반복문)로 푸는 것이 더 빠를 수 있다 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ..

Algorithm/알고리즘 [Algorithm] 클루스칼 알고리즘 (Kruskal Algorithm) 1. 신장트리란? 그래프에서 1) 모든 노드를 포함하면서 2) 사이클이 존재하지 않는 부분 그래프를 의미 이는 트리의 조건이기도 함 2 . 최소신장트리 최소의 비용으로 구성되는 신장 트리를 찾아야 할 때 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결 될 수 있게 도로를 설치하는 경우 3. 크루스칼 알고리즘 가장 대표적인 최소 신장 트리 알고리즘 그리디 알고리즘으로 분류 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 → 최소 신장 트리에 포함 사이클이 발생하는 경우 → 최소 신장 트리에 포함 X 모든 간선에 대하여 2번의 과정을 반복 결론 최소 신장 트리에 포함되어 있..

Algorithm/알고리즘 [Algorithm] 그리디 알고리즘 1. 정의 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많지만, 코딩테스트에서는 대부분 그리디로 풀었을 때 최적의 해가 됨 2. 대표적인 그리디 문제 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원입니ㅏㄷ. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 500원, 100원, 50원 10원짜리 동전에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?만약, 800원을 거슬러주어야하는데, 500원, 400원, 100원..

이전 1 다음

티스토리툴바