본문 바로가기

coding5

[코딩 테스트 공부] Ch7. 이진 탐색 순차 탐색(처음부터 순차적): 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1시간 복잡도 : O(N)이진 탐색(반으로 쪼개면서 탐색): 탐색 범위를 절반씩 좁혀가며 데이털르 탐색배열이 정렬되어 있을 때 사용 가능변수 3개 사용 → 시작점, 끝점, 중간점def binary_search(array, target, start, end): if start > end: return none mid = (start + end) // 2 if array[mid] == target: retur.. 2026. 3. 25.
[코딩 테스트 공부] Ch.6 정렬 Sorting(정렬): 데이터를 특정한 기준에 따라서 순서대로 나열정렬 알고리즘 사용하면, 이후 배울 Binary Search 알고리즘도 사용할 수 있다.종류: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬선택 정렬(가장 작은 것을 선택): 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복시간 복잡도 = O(n^2)array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 7]for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j # Swap 사용 arr.. 2026. 3. 20.
[코딩 테스트 공부] Ch5. DFS/BFS Search: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정Data Structure: 데이터를 표현하고 관리하고 처리하기 위한 구조Stack(스택)선입후출명령어: append(값), pop()Queue(큐)선입선출명령어(from collections import deque): append(값), popleft(), popright()출력 시, list(queue)로 하면 리스트 자료형이 반환된다.재귀 함수자기 자신을 다시 호출하는 함수def recursive_func(i): if i == 100: return print(i, '번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출합니다.') recursive_func(i+1) print(i, '번째 재귀 함수를 종료합니다.') recursiv.. 2026. 3. 20.
[코딩 테스트 공부] Ch4. 구현 ‘구현’ : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정→ 어떤 문제를 풀든, 소스코드 작성 과정은 필수이므로, 구현 문제 유형은 모든 범위의 코테 유형을 포함한다.‘구현’ 유형완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 직접 수행구현 시 고려해야 할 메모리 제약 사항나는 파이썬으로 코딩 테스트를 볼 것이므로 파이썬의 경우만 살펴보자.파이썬에서 리스트 크기데이터 개수(리스트 길이)메모리1,0004KB1,000,0004MB1,000,000,00040MB그리고 “python3” 보다 “PyPy3” 이 실행속도가 훨씬 빠르다.구현 알고리즘의 대표적 예시 2가지상하좌우 문제: 좌표 n*n에서 현재 위치(1,1)에 서있는 여행가가 입력을 받은.. 2026. 3. 20.
[코딩 테스트 공부] 그리디 백준 티어를 올리기 위해 코딩 테스트, 줄여서 코테 공부도 시작했다..! '그리디'부터 배워볼 것이다. 그리디 : '탐욕법'이라는 뜻으로, 현재 상황에서 지금 당장 좋은 것만 고르는 방법그리디 알고리즘 : 기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 문제에서 기준을 제시해 준다. 대체로는 정렬 알고리즘을 사용하므로, 그리디 알고리즘과 정렬 알고리즘은 자주 짝을 이뤄 출제된다.그리디 알고리즘의 정당성그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 처음 문제를 만나고 바로 문제 유형을 찾기 어렵다면, 그리디 알고리즘을 먼저 의심해보자.그럼에도 풀리지 않다면 뒤에 나오는 다이내믹 프로그래밍이나 그래프 알고리즘 등으로 재차 .. 2025. 3. 23.

티스토리툴바