본문 바로가기

전체 글86

[알고리즘] 5. 이진 탐색 /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 이진 탐색 알고리즘 - 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법 (순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법) - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. - 단계마다 탐색 범위를 2로 나누느 것과 동일하므로 연산 횟수는 logN에 비례한다. - 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다. def binary_search(start, end, target, array): if start > .. 2022. 1. 4.
[알고리즘] 4. 정렬 알고리즘 /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 정렬 알고리즘 - 정렬 (sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. - 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 2. 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array) - 1): for j in range(i+1, len(array)): if array[i] > array[j]: array[i], arr.. 2022. 1. 3.
[알고리즘] 3. BFS & DFS /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 그래프 탐색 알고리즘 - 탐색 (search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. - DFS / BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. 2. 스택 자료구조 - 먼저 들어 온 데이터가 나중에 나가는 형식 (선입후출 - FILO)의 자료구조 - 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 2-*. 스택 구현 stack = [] stack.append(1) stack.append(2) stack.append(3) stack.append(.. 2022. 1. 3.
[알고리즘] 2. 구현 (implementation) /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 구현 (implementation) - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 알고리즘 대회에서의 구현 유형의 문제란? : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. - 구현 유형의 예시는 다음과 같다. 1) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 2) 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 3) 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 4) 적절한 라이브러리를 찾아서 사용해야 하는 문제 - 구현 문제에서 자주 등장하는 '행렬 (matrix)' for i in range(.. 2021. 12. 27.

티스토리툴바