Binary Search 📝 간단한 개념정리 이진 탐색 : 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 것이 이진 탐색 과정이다. 시간복잡도 : O(logN) 👆🏻 Binary Search Python으로 구현 def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mid if arr[mid] < target: low = mid + 1 return -1 arr = ["A", "B", "C", "D", "E", "F", "G", "H", ..

DFS / BFS 📝 간단한 개념정리 DFS(Depth-First-Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. BFS(Breadth-First-Search) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘. DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 이용 큐 자료구조 이용 👆🏻 DFS Python으로 구현 # DFS def dfs(graph, v, visited): # 현재노드 방문처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: # 방문한 노드인지 확인 if not visited[i]: dfs(graph, i, visited) # 나중..

오늘은 최단경로를 공부한 내용을 가지고 포스팅한다. 최단경로(Shortest Path) 알고리즘은 말그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘은 다양한 종류가 있고 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있는 상태이다. ex) 1. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 참고로 코딩테스트에서는 주로 최단경로를 모두 출력하는 문제보다는 최단 거리를 출력하는 문제가 많이 출제되는 경향이 있다. 1. 가장 빠른 길 찾기 - 최단 경로 알고리즘 - 특징 컴퓨터공학과 학부 수준에서는 다익스트라 / 플로이드 워셜 / 벨만 포드 알고리즘 이렇게 3가지가 있음 그리디 알고리즘과 다이나믹 프로그래밍..

이번에는 Chapter8 다이나믹 프로그래밍을 공부할 차례다. 다이나믹 프로그래밍은 연산 속도 한계 및 메모리 공간 한정이라는 컴퓨터의 제약 사항들을 극복하고자 하는 기법이다. 동적 계획법이라고도 하며 탑다운과 보텀업 2가지 방식이 존재한다. 해당 방식 모두 공부하고 마지막으로는 다이나믹 프로그래밍에 자주 사용되는 메모이제이션 기법까지 공부한다. ※ 주의할점 다이나믹 프로그래밍과 동적 할당의 다이나믹은 다른 의미임. 1. 중복되는 연산을 줄이자 - 다이나믹 프로그래밍(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (출처 : 위키백과) 수열 시간 복잡도 O(N) Top-Down(메모이제이션, 하향식) 방식 : 큰 문제를 해결하기 위해 작은 문제 호출(재귀..

오늘은 이진탐색에 대한 주제의 포스팅이다. 이진탐색 알고리즘은 리스트 내에서 데이터를 매우 빠르게 탐색한다. 일단 이진탐색을 알아보기 이전에 순차 탐색부터 알아보겠다. 1. 범위를 반씩 좁혀가는 탐색 - 순차탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서 데이터를 하나씩 차례대로 확인하는 알고리즘 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있음. 시간 복잡도 O(N) - 순차탐색 활용 리스트 내 특정 값의 원소가 있는지 체크할 때 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때 내부에서 순차탐색 수행 - 이진 탐색 ..

Part2 주요 알고리즘 이론과 실전문제의 Chapter6 정렬을 공부할 시간이다. 7월-12월간의 교육이 끝나고 이제부터 취업전선에 뛰어들기 전에 코딩테스트 실력을 갈고닦기 위해 다시 [이것이 코딩테스트다]로 공부중이다. 이번주에는 Part2 1회독을 한 후에 다음주부터 실전문제를 풀 예정이다. 그리고 1회독을 한 것을 기반으로 다시 머릿속으로 정리하려고 블로그에 포스팅 한다. 1. 정렬 - 정렬 : 데이터를 특정간 기준에 따라서 순서대로 나열하는 것 - 종류와 시간복잡도 내용 시간복잡도 선택 정렬 (Selection Sort) - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복 O(N제곱) 삽입 정렬 (Insetion..

책의 Chapter5에 등장하는 DFS/BFS에 대해 공부하는 시간이다. 1. 꼭 필요한 자료구조 기초 - 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐 삽입(Push) : 데이터 삽입 삭제(Pop) : 데이터 삭제 - 스택 : 선입후출 구조 또는 후입선출 구조 빈 배열 선언 append 함수로 데이터 삽입 pop 함수로 데이터 삭제 stack = [] stack.append(8) stack.append(0) stack.append(7) stack.pop() # pop은 가장 뒤쪽(오른쪽)에 있는 데이터를 꺼냄. stack.append(6) stack.append(0) pri..

책의 2부에서 처음으로 등장하는 구현에 대해 공부하는 시간이다. 1. 구현 - 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 특징 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제 라이브러리 사용 경험이 많다면 유리(ex. 순열 문제의 경우 itertools로 쉽게 짜기 가능) 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 - 메모리 제약 사항 고려하기!(with Python) 대체로 코딩 테스트에서는 128 ~ 512 MB로 메모리 제한 BUT..