algorithm
-
PART02 - CHAPTER 05. DFS/BFSalgorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 24. 12:49
1. 꼭 필요한 자료구조 기초 - 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. - 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. - 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. - 그런데 DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀 함수를 간단히 정리하고자 한다. - 자료 구조(Data Structure)란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. - 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로..
-
PART02 - CHAPTER 04. 구현algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 24. 12:47
1. 아이디어를 코드로 바꾸는 구현 피지컬로 승부하기 - 코딩테스트에서 구현(Implementation) 이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. - 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. - 이 구현 유형의 문제들을 보면 '알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는게 좋다'라고 설명한다. - 어떤 문제가 구현하기 어려운 문제일까? ㆍ알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 ㆍ특정 소수점 자리까지 출력해야하는 문제 ㆍ문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제 - 이 책에서는 완전탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다..
-
PART02 - CHAPTER 03. 그리디algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 24. 12:46
1. 당장 좋은 것만 선택하는 그리디 - 그리디 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. ㆍ현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. - 정렬, 최단 경로 등의 알고리즘 유형은 이미 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. - 예를 들어 여러 개의 데이터를 빠르게 정렬해야 하는 문제는 정렬 라이브러리의 사용 방법을 알고 있어야한다. 또 다른 예시로 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜 혹은 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있어야한다. - 그리디 알고리즘은..
-
이것이 취업을 위한 코딩테스트다 - 1. 코딩 테스트 개요algorithm/이것이 취업을 위한 코딩테스트다 2022. 6. 13. 18:37
복잡도( Complexity ) - 복잡도는 알고리즘의 성능을 나타내는 척도 - 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 ( Time Complexity ) ㆍ특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미 ㆍ알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 ( Space Complexity ) ㆍ특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 ㆍ알고리즘을 위해 필요한 메모리의 양 * 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법 시간 복잡도 - 알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간복잡도를 의미한다. - 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과 ( Time Limit ..