이진 탐색이진 탐색을 사용하면 리스트 내에서 데이터를 매우 빠르게 탐색할 수 있다. 이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다.순차 탐색 : 리스트 내의 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법데이터의 정렬 여부와 관계없이 가장 앞에 있는 원소부터 하나씩 확인데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로 시간 복잡도는 O(N)개념 정리이진 탐색배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘필요한 변수 : 시작점, 끝점, 중간점찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교단계마다 2로 나누는 것과 동일하므로 시간 복잡도는 O(logN)예시 : 값이 4인 카드 탐색시작점..
정렬개념 정리정렬데이터를 특정한 기준에 따라서 순서대로 나열하는 것예) 카드 크기에 따라 순서대로 나열하도록 하는 것특징프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나데이터를 정렬하면 이진 탐색 (Binary Search)이 가능 (다음 챕터 내용)정렬 알고리즘 소개 다양한 알고리즘이 존재하지만, 이 중에 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 소개하려고 한다. 여기서는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다.아래의 카드를 기준으로 정렬 알고리즘 설명 진행선택 정렬매번 가장 작은 것을 선택해 앞의 데이터와 변경하여 정렬알고리즘가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 변경다음으로 작은 데이터를 선택..
DFS & BFS탐색 (Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS, BFS가 있다. 이를 이해하기 위해 몇 개의 자료구조를 먼저 알아봐야 한다.자료구조 기초스택 (Stack)선입후출(FILO) or 후입선출(LIFO) : 나중에 들어온 것이 먼저 나감Python의 list : 삽입(append), 삭제(pop)예시 : (박스 쌓기) 아래에서 위로 쌓고 아래의 박스를 치우기 위해 위의 박스를 먼저 내려야 함큐 (Queue)선입선출(FIFO) : 먼저 들어온 것이 먼저 나감python의 deque : 삽입(append), 삭제(popleft)예시 : (대기 줄) 입..
구현개념 정리피지컬로 승부하기코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'프로그래밍 언어의 문법을 이해하고 문제의 답안 코드를 실수 없이 작성해야 함프로그래밍 문법을 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 불리완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행변수의 표현 범위 C / C++ / Java : int, long long 등 종류에 따라 표현 범위가 달라짐Python : 프로그래머가 직접 자료형을 지정할 필요가 없고 큰 수의 연산을 기본으로 지원파이썬 리스트 크기대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한파이썬은 시스템 내부적으로 아래와 유사한 크기의..
