푸으름

Algorithm 공부 #06 - 정렬(삽입 정렬과 퀵 정렬) 삽입 정렬(Insertion Sort) ● 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하며 정렬하는 방식 ● 시간 복잡도는 O(n^2)으로 느린 편이지만 구현 난이도는 쉬움 ● 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하여 시간 복잡도 줄일 수 있음 ● 삽입 정렬 과정 1. 현재 index에 있는 데이터 값을 선택 2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색 3. 삽입 위치부터 index가 있는 위치까지 shift 연산을 수행 4. 삽입 위치에 현재 선택한 데이터를 삽입하고 indexx++ 연산을 수행 5. 현재 데이터의 크기만큼 index가 커질 때까지, ..

Algorithm 공부 #04 - 자료구조(스택과 큐) 스택(Stack) ● 후입선출 구조로 삽입과 삭제가 한 쪽에서만 일어나는 자료구조 ● 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에서 효과적 https://pooreumjung.tistory.com/39 큐(Queue) ● 선입선출 구조로 삽입과 삭제가 양방향에서 일어나는 자료구조 ● 너비 우선 탐색(BFS) 종류의 코딩 테스트에서 효과적임 https://pooreumjung.tistory.com/25 ● 우선순위 큐(priority queue) : 값이 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 예제 백준 1874번 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 ..

Algorithm 공부 #01 - 시간 복잡도와 디버깅 시간 복잡도 ● C++에서는 1억 번의 연산을 1초의 수행 시간으로 예측한다 ● 시간 복잡도 → 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도로 총 3가지의 표기법이 있음 1. 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 2. 빅-세타( : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 3. 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 ※ 코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하기 ● 시간 복잡도 도출 기준 1. 상수는 시간 복잡도 계산에서 제외한다. 2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 ..