이전 포스팅 더보기 Chapter 6. 정렬(1) 실전문제 1. 위에서 아래로 하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다. 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1
다음 포스팅 더보기 Chapter 6. 정렬(2) 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 굉장히 다양한데 이중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 알아보도록 하자. 오름차순을 내림차순으로, 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다. 우선 오름차순을 기준으로 알아보도록 하자. 선택 정렬 선택 정렬(Selection Sort) 알고리즘은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것이다. 원시적으로 매번 '가장 작은 것을 선택'한다는 것이다. 간단하게 보면 다음과 같다. 1. 가장 작은 데이터를 찾는다. 2. 맨 앞..
꼭 필요한 자료구조 기초 탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS/BFS가 대표적인 탐색 알고리즘이다. 자료구조(Data structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 스택과 큐가 대표적인 자료구조로 이들은 삽입(Push), 삭제(Pop)의 두 핵심적인 함수로 구성된다. 실제로 스택과 큐를 사용할 때는 삽입, 삭제 외에도 오버플로와 언더플로를 생각해야한다. 오버플로(Overflow) - 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입할 때 발생하는 것이다. 언더플로(Underflow) - 특정 자료구조에 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생하는 것이다. 스택(St..
구현(implementation) 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 코딩 테스트에서는 알고리즘은 아니지만 이 구현이 중심이 되는 문제가 자주 출제된다. 구현 문제는 흔히 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 이런 구현하기 어려운 문제의 예시로는 아래와 같다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제 해당 책에서는 '완전 탐색', '시뮬레이션' 유형을 모두 이 '구현' 유형으로 묶어서 생각한다. 둘 다 구현의 핵심이 되는 경우가 많다. 완전 탐색(Brute Force) - ..
그리디 알고리즘(Greedy Algorithm) 당장 좋은 것만 선택하는 방법을 그리디(탐욕법) 알고리즘이라고 하며 단순하지만 강력한 문제 해결 방법이다. 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만을 고르는 방법'을 의미한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 이는 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.(정렬, 최단 경로 등의 알고리즘 유형의 경우 미리 알고리즘 사용 방법을 숙지하고 있어야 해결 가능한 경우가 많다.) 그리디 알고리즘 자체가 문제 출제 폭이 매우 넓기 때문에 최단 경로 알고리즘에 속하는 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘이므로 그리디 알고리즘이면서도 '암기'가 필요한 알고리즘도 있을 수 있..
