알고리즘/알고리즘공부

[이코테] 스택, 큐, 재귀

탐색 (Search) 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이며, 대표적인 탐색 알고리즘으로 DFS, BFS가 존재함  DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택, 큐와 재귀에 대한 이해가 있어야함 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조로, 스택과 큐는 자료구조의 기초 개념 : 자료구조의 기초 개념으로 삽입(Push), 삭제(Pop) 등의 핵심적인 함수로 구성됨 스택 스택은 박스 쌓기로 비유할 수 있음. 박스를 쌓을 때는 아래에서 위로 차곡차곡 쌓으며, 박스를 치울 때는 위에서 박스를 내려야함 이처럼, 선입후출(FILO - First In Last Out) 구조 또는 후입선출(LIFO - Last In First Out..

[이코테] 구현

구현 코딩 테스트에서 구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정' 문제 해결 분야에서 구현 유형의 문제는 '풀이는 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미 문제가 구현하기 어려운 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야(파싱) 하는 문제, 적절한 라이브러리를 찾아서 사용해야 하는 문제 등이 있음 [이코테] 책에선 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룸. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형..

[이코테] 그리디 알고리즘

그리디 알고리즘 (탐욕법) 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시함 [ 예제 3-1 ] 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10배수이다. 문제 접근 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이 아이디어의 핵심 예를 들어 N원을 거슬러 준다고 할 때, 500원으로..