본문 바로가기

전체 글502

Advanced Algorithm - 탐욕(Greedy) 알고리즘 1. 탐욕 알고리즘 이란? - 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘이다. - 여러가지 경우 중 하나를 결정해야할 때, 상황에 따라 매순간 최선의/최적의 경우를 선택하여 최종적인 값을 구하는 방식이다. - 다시 말해, 문제를 풀기위해 최선의 경우를 선택하는 방식 2. 탐욕 알고리즘의 예 a) 동전 문제 - 지불해야 하는 값이 4720원 일 때, 1원 40원 100원 500원짜리 동전을 사용하여 가장 적은 동전 수를 이루는 조합을 찾아라. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 된다. coin_list = [1,50,100,500] def min_coin_count(value, coin_list):.. 2020. 9. 26.
Advanced Algorithm - 깊이 우선 탐색(Depth First Search) 1. 깊이 우선 탐색(DFS)이란? - 방향과 상관없이 오른쪽 또는 왼쪽 노드를 기준으로, 한 노드의 자식노드를 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가는 방식으로 순회하는 탐색 a) DFS 예시 DFS 동작방식: A - B - D - E - F - C - G - H - I - J 2. DFS 알고리즘 동작방식의 이해 - DFS 알고리즘은 Stack과 Queue를 이용하여 구현할 수 있다. - need_visit Stack과 visited Queue를 사용하여 구현한다. - stack의 특성(LIFO)으로 인해 BFS와는 다르게 need_visit Stack에서 꺼내오는 데이터는 가장 나중에 삽입된 데이터다. 3. DFS 알고리즘 코드구현 def dfs(graph, star.. 2020. 9. 25.
Advanced Algorithm - 너비 우선 탐색(Breadth First Search) 1. 그래프 탐색 알고리즘이란? - 그래프를 기반으로 특정 노드를 찾아가기 위한 알고리즘 - 이 그래프 알고리즘에는 2가지 대표 알고리즘이 있다. 너비 우선 탐색(Breadth First Search) - 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search) - 정점(노드)의 자식노드를 먼저 탐색하는 방식 a) 너비 우선 탐색(BFS)의 예 - 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로, 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드(형제 노드)를 먼저 순회하는 탐색 BFS 이동순서: A - B - C - D - G - H - I - E - F - J b) 깊이 우선 탐색(DFS)의 예 - 방향과 상관없이 왼쪽 또는.. 2020. 9. 24.
Advanced Algorithm - 그래프의 이해(basic concepts of the graph) 1. 그래프(Graph) 란? - 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위한 방법 ex) 집에서 회사로가는 경로를 그래프로 표현 a) 그래프 관련 용어 정리 노드(Node): 위치를 말함, 정점(Vertex)라고도 함 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 정점(vertex) 또는 인접 정점 (Adjacent Vertex): 간선과 직접 연결된 정점(또는 노드) ex) 집과 지하철, 집과 버스, 버스와 회사, 지하철과 회사 추가 참고 용어 - 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 (In-Degree): 방.. 2020. 9. 23.
Advanced Algorithm - 순차 탐색(Sequential Search) 1. 순차 탐색이란? - 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교하여 원하는 데이터를 찾는 방법 2. 코드구현 a) random 라이브러리를 이용하여 리스트 생성 import random data_list = random.sample(range(100), 10) print(data_list) b) Sequential Search 함수 구현 def sequential(data_list, search_data): for index in range(len(data_list)): if data_list[index] == search_data: return index return -1 c) 테스트 3. 순차 탐색의 시간복잡도 - 찾는 데이터가 리스트에 존재하지 않는다면, 최악의 경우 O(n)만큼의 시간복.. 2020. 9. 22.
코코아톡(HTML/CSS) 1. 개요 - 카카오톡 메신저의 UI를 HTML/CSS만 이용하여 카피하면서 HTML/CSS의 기본 사용법과 웹의 기본 구조를 익히고 공부하기 위해 진행한 프로젝트입니다. 2. 사용한 기술 - HTML/CSS 3. Github https://github.com/devraphy/kakao-clone GitHub - devraphy/kakao-clone: Repository for the KakaoTalk interface cloning portfolio Repository for the KakaoTalk interface cloning portfolio - GitHub - devraphy/kakao-clone: Repository for the KakaoTalk interface cloning portfo.. 2020. 9. 20.
Advanced Algorithm - 이진 탐색(Binary Search) 1. 시작하기 전에 - 아래와 같은 문제가 있을 때, 어떤 방법(=알고리즘)을 사용하는 것이 가장 효율이 좋을지 생각해보자. 생각의 과정 1. 조건 점검하기 - 1~100 사이의 난수가 30개의 병뚜껑에 적혀있고 이 중에 70이 있는지 찾아야 한다. - 30개의 병뚜껑에는 오름차순으로 숫자가 정렬되어 있다. - 가장 적은 수의 병을 따서 70을 찾아야 한다. 2. 가장 적은 수의 병을 따는 방법 - 1~30번 후보군의 중간에 위치한 15번 병뚜껑을 확인하여 후보군을 반으로 줄인다. - 15번 병뚜껑의 숫자가 70보다 작다면 우측(16 ~ 30번 병뚜껑), 70보다 크다면 좌측(1~14번 병뚜껑)을 후보군으로 선정한다. - 좌측 또는 우측의 후보군이 선정되면 위의 과정을 반복한다. - 최종적으로 숫자 70.. 2020. 9. 18.
Advanced Algorithm - 병합 정렬 (Merge Sort) 1. 병합 정렬이란? - 분할 정복 알고리즘을 기반한 정렬이다. - 재귀용법을 사용한다. a) 병합 정렬의 동작 방식 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 어떻게 구현할까? 필요한 기능 1. 단위 데이터까지 나누는 기능 * 단위 데이터: 더 이상 분리될 수 없는 데이터 2. 나눠진 데이터를 정렬하면서 합치는 기능 3. 재귀 용법을 활용하여 1번과 2번 기능을 구현 3. 코드 구현 1) 리스트를 분리하는 기능 def split(data): medium = int(len(data) / 2) #리스트의 중간위치 left = data[:medium].. 2020. 9. 17.
Advanced Algorithm - 퀵 정렬(Quick Sort) 1. Quick 정렬이란? - 정렬 알고리즘의 꽃! 파이썬과 만나면 아름다운 코드가 탄생한다. - 데이터에서 기준점(pivot)을 정하여 pivot보다 작다면 좌측(left)에, 크다면 우측(right)에 정렬한다. - 좌/우측으로 1차 정렬된 데이터에서 좌/우측 각각의 pivot을 다시 선정하고 정렬을 수행한다. - 이 과정을 재귀함수를 사용하여 반복한다. - 최종적으로 정렬된 데이터를 반환한다. 예시) Quick 정렬의 동작과정 index 0 1 2 3 4 5 data 55 13 45 88 76 59 이와 같은 데이터가 있을 경우, 1) 55를 pivot으로, 좌/우측으로 정렬 index 1 2 0 3 4 5 data 13 45 55 (pivot) 88 76 59 2) 좌/우측에서 각각 pivot을 .. 2020. 9. 15.
Advanced Algorithm - 동적 계획법(DP) & 분할정복(Divide&Conquer) 1. 정의 1) 동적 계획법(Dynamic Programming, DP) - 정의: 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘 - 상향식 접근법: 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 - 메모이제이션(Memoization) 기법: 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 왜 이런 기법들을 사용하는가? → 큰 문제를 작게 쪼개어 풀다보면 중복되는 부분이 발생한다. 동일한 연산에 대해서는 1번의 연산을 수행하여 저장하는 방식을 통해 이를 재활.. 2020. 9. 15.
Algorithm - 재귀함수/호출 연습 (recursion practice) 문제 1) 재귀함수를 이용하여 1부터 n까지의 곱셈을 구현하라. 1) for문을 이용한 코드 def multiple(num): return_value = 1 for index in range(1, num+1): return_value = return_value * index return return_value [결과] 2) 재귀함수를 이용한 코드 def multiple(num): if num 2020. 9. 12.
Algorithm - 재귀 호출(Recursive Call) 1. 재귀 호출(recursive call) - 재귀 호출이란, 함수 안에서 해당 함수가 호출되는 형태를 말한다. - 고급 알고리즘을 이해하기 위해 반드시 이해해야 하는 개념이다. 1) 팩토리얼 알고리즘을 재귀호출을 이용하여 구현 a) 간단한 경우부터 생각해보기 * 2! = 1 X 2 * 3! = 1 X 2 X 3 * 4! = 1 X 2 X 3 X 4 = 4 X 3! b) 규칙이 보임: n! = n X (n - 1)! 1. 함수를 하나 만든다. 2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1) 3. 함수(n) 은 n = 1 이면 return n c) 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함) 1. 먼저 2! 부터 - 함수(2) 이면, 2 > 1 이므.. 2020. 9. 11.

티스토리툴바