본문 바로가기

윤코딩

Notice

Recent Posts

Popular Posts

Recent Comments

Link

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

기본알고리즘

코딩테스트/기본 알고리즘 2022. 2. 20. 다이나믹 프로그래밍(Dynamic_Programming) 1. Dynamic_Programming 이란 큰문제를 작은 문제로 나눌 때 주로 사용한다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할때 사용할 수 있다. 주의사항 : 재귀함수로 다이나믹 프로그래밍을 구현시 재귀함수를 적재하는 메모리에서 오버헤드가 발생할수있다. 따라서 다이나믹 프로그래밍에서는 재귀함수보다 반복문을 사용하여 오버헤드를 줄일 수 있다. 피보나치 수열은 다이나믹 프로그래밍의 대표 문제이다. 파보나치를 통해 다이나믹 함수를 이해해보자. 2. 예시코드(재귀함수 사용) d = [0] * 100 # 한 번 계산된 결과를 메모이제이션(memoization)하기 위한 리스트 초기화 def fibo(x): # 피보나치 수열을 재귀함수로 구현(탑 다운 다이나믹 프로그래밍) if x =..

코딩테스트/기본 알고리즘 2022. 2. 20. 순차탐색(Sequential_Search) Sequential_Search(순차 탐색) 1. Sequential_Search란 탐색 알고리즘 중 가장 간단한 알고리즘으로 단순히 앞에서부터 순차적으로 비교하며 찾아간다. 구현이 간단하지만 효율적이지 못하다. 2. 예시 코드 def sequential_search(n, target, array): # n : 문자열개수, target : 찾을값, array : 문자열 리스트 for i in range(n): if array[i] == target: # array[0]부터 순차적으로 target과 같은지 탐색한다. return i + 1 # i는 0부터 이므로 + 1

코딩테스트/기본 알고리즘 2022. 2. 20. 이진탐색(Binary_Search) Binary_Search(이진 탐색) 1. Binary_Search란 배열의 내부 데이터가 정렬되어 있어야 사용가능한 알고리즘으로 조건만 맞다면 매우 빠르다. (O(logn)의 시간복잡도) 데이터를 절반씩 좁혀가므로 위치를 나타내는 변수 (시작점, 중간점, 끝점) 3개가 필요하다. 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하는것이 진행방식이다. 2. 예시코드 2.1 재귀함수 방식 def binary_search(array, target, start, end): if start > end: # array에 target값이 존재하지 않아 계속된 재귀함수 호출로 start > end가 된경우 None return return None mid = (start + end) // 2 # 중간점 if ..

코딩테스트/기본 알고리즘 2022. 2. 20. 깊이 우선 탐색(DFS) DFS(깊이 우선 탐색) 1. DFS(Depth First Search)란? 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 방법이다. 그래프는 노드(Node)와 간선(Edge)로 표현되며 노드는 정점(Vertex)라고도 한다. 그래프는 인접리스트(리스트로 그래프의 연결관계 표현)와 인접행렬(2차원 배열로 그래프의 연결 관계를 표현)로 표현할 수 있다. DFS(깊이우선탐색)는 스택 자료구조를 사용하며 동작과정은 아래와 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번위 과정을 더 ..

코딩테스트/기본 알고리즘 2022. 2. 20. 너비 우선 탐색(BFS) BFS(너비 우선 탐색) 1. BFS(Breadth-First Search)란? BFS알고리즘은 너비 우선 탐색이란 의미를 가진다. 이는 가까운 노드부터 탐색하는 알고리즘이란 뜻이다. DFS는 최대한 멀리있는(깊은) 노드부터 탐색하는것에 비해 BFS는 가까운 노드부터 탐색하므로 이 두개를 적절하게 사용해야 한다. BFS 구현에서는 선입선출, 즉 큐 자료구조를 사용하는것이 정석이다. BFS 알고리즘의 동작방식에는 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 2. 예시 코드 from collections import d..

이전 1 다음

티스토리툴바