※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다. 📚 선택 정렬Selection Sort 매번 가장 작은 데이터를 선택해서 앞으로 보내는 과정을 반복 수행하여 전체 데이터를 정렬. array = [7, 5, 9, 0, 3] 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] # 스와프 print(array) 선택 정렬의 시간 복잡도 : O(N²) 📚 삽입 정렬Inser..

📚 DFS (Depth-First Search) '깊이 우선 탐색'이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. ✅ 동작 과정 ( Stack 이용 ) 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2️⃣ Stack 의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 Stack 에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 Stack 에서 최상단 노드를 꺼낸다. 3️⃣ 2️⃣번 과정을 더 이상 수행할 수 없을 때까지 반복한다. * '방문처리' 는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체..

📚 구현 - 완전탐색, 시뮬레이션 구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 📃 [예제 1] 상하좌우 - 풀이시간 : 13분 - 문제풀이 # 1. 나의 풀이 n = int(input()) map = list(map(str, input().upper().split())) x,y = 1,1 for m in map: if m == 'R': y = y+1 if y+1 = 1 else y if m == 'U': x = x-1 if x-1 >= 1 else x ..

📚 복잡도 복잡도는 알고리즘의 성능을 나타내는 척도이다. 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 복잡도를 측정함으로써 시간 복잡도에서는 알고리즘을 의해 필요한 연산의 횟수를, 공간 복잡도에서는 메모리의 양을 계산할 수 있다. 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. ⚡ 시간 복잡도 시간 복잡도를 표현할 때는 빅오Big-O 표기법을 사용한다. 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다. [예제 1] 시간 복잡도 O(N) 5개의 데이터를 받아 차례로 5회 더해준다(N = 5). 이 때 연산횟수는 N에 비례하는 것..

📚 그리디 (Greedy) 알고리즘 '탐욕법'이라고도 소개되는 이 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 단순하지만 강력한 문제 해결 방법 매 순간 가장 좋아보이는 것을 선택. 현재의 선택이 나중에 미칠 여향에 대해서는 고려하지 않는다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 📃 [예제 1] 거스름돈 - 풀이시간 : 15분 - 문제풀이 n = 1260 count = 0 # 큰 단위의 화폐부터 차례대로 확인 list = [500, 100, 50, 10] for coin in list: count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기..