투 포인터(Two Point)

출처 : https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=40 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 흔히 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 간단히 "2번부터 7번까지의 학생"이라고 부르곤 한다. 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터 문제를 활용해서 해결할 수 있는 가장 대표적인 문제는 특정한 합을 가지는 부분 연속 수열 찾기 문제이다. (부분 연속 수열이란, 하나의 수열이 있을 때 그 수열에서 연속..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 8. 4.
• textsms

최단 경로 알고리즘 - 플로이드 워셜 알고리즘

https://www.youtube.com/watch?v=acqm9mM1P6o&t=831s 플로이드 워셜 알고리즘 개요 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 플로이드 워셜은 점화식에 맞게 3중 반복문을 통해서 2차원 테이블을 갱신해주는 방식으로 동작한다. 다익스트라 알고리즘보다 구현 난이도는 쉽지만, 시간 복잡도는 O(N3..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 30.
• textsms

최단 경로 알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)

출처 : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 ex) 1~6번의 노드가 존재한다. 이때, 각 노드는 문제 상황에 따라 국가, 도시 등 다양한 형태로 표현될 수 있다. 또한 1번 노드에서 2번 노드로 이동이 가능하다면, 위 그림과 같이 표현이 가능하다. 이런 간선은 문제 상황에 따라 도..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 30.
• textsms

이진 탐색

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이진 탐색 알고리즘 ​ · 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 ​ · 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 · 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. ​ 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾아보자. ​ 먼저 시작점은 제일 왼쪽에 있는 0번째 인덱스, 끝점은 가장 오른쪽에 있는 9번째 인덱스 그리고 중간점은 가운데 4번째 인덱스로 설정한다. 만약 중간값이 2개가 있으면 소수점을 제거한 값이 ..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms

정렬 알고리즘 (2) [퀵 정렬, 계수 정렬]

https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 ​ 3. 퀵 정렬 · 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. · 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다. · 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다. · 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다. ​ 맨 처음 피벗의 값은 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 그 뒤, 이 두 데..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms

정렬 알고리즘 (1) [선택 정렬, 삽입 정렬]

https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 정렬 알고리즘 · 정렬이란 데이터를 특정 기준에 따라 순서대로 나열하는 것 · 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. ​ ​ 1. 선택 정렬 알고리즘 · 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘 ​ 정렬 되지 않은 데이터 맨 처음 위와 같이 정렬 되어있지 않은 데이터가 존재한다고 가정해보자. ​ 처리 되지 않은 데이터 중 가장 작은 값인 '0'을 선택해 가장 앞에 있는 '7'과 교환한다. ​ 다시 처리되지 않은 데이터 중 가장 작은 값인 '..

• format_list_bulleted 코딩테스트 준비/이것이 코딩테스트다 개념정리
• · 2023. 6. 15.
• textsms