Algorithm
5. [Algorithm] 이진 탐색
5. [Algorithm] 이진 탐색
2023.03.20이진 탐색 / 이분 탐색 (Binary Search) 이진 탐색 (이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색 은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 이진 탐색 / 이분 탐색 알고리즘 코드 (Python) # 재귀 함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 원하는 ..
4. [Algorithm] 정렬
4. [Algorithm] 정렬
2023.03.20정렬 알고리즘 (Sorting Algorithm) 정렬(Sorting) 이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해진다. (정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하므로 중요하다.) 다양한 정렬 알고리즘에 대해서 알아보자. 선택 정렬 (Selection Sort) 선택 정렬 은 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 한다. 즉, 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 2번째 데이터와 바꾸는 과정을 반복한다...
3. [Algorithm] DFS / BFS
3. [Algorithm] DFS / BFS
2023.03.14DFS / BFS DFS와 BFS를 알기 위한 그래프 개념 그래프란? 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점이라고 한다. 그래프 탐색이란? 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 먼저 그래프에 대해 알아보자. 두 노드가 엣지로 연결되어 있을 때 ex) 위 그림에서 A-B 가 연결되어있는데, 이때, '두 노드가 인접한다(Adjacent)' 라고 표현한다. 프로그래밍에서는 그래프를 표현하는 2가지 방식이 있다. 1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현 2. 인접 리스트(Adjaceny List) : 리스트로 그래프의 연결 관계를 표현 인접 행렬로 표현한 그래프 0 1 2 0 0 5 7 1 5 0 무한 2 7 무..
2. [Algorithm] 구현(시뮬레이션, 완전탐색)
2. [Algorithm] 구현(시뮬레이션, 완전탐색)
2023.03.06구현 나의 생각을 소스코드로 바꾸는 과정이다. 코딩 테스트를 풀기 위해서는 소스코드를 작성하는 과정은 필수 → 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념. 생각해낸 문제 해결 방법을 내가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해서는 해당 언어의 문법과 문제의 요구사항을 정확히 알고있어야 한다. 완전 탐색(Brute Force), 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다.(이코테 도서) 완전 탐색(Brute Force) : 모든 경우의 수를 주저 없이 다 계산하는 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하여 해결하는 방법 그렇다면, 어떠한 문제 유형이 구현하는데 까다로울까? ex) 알..
1. [Algorithm] 그리디
1. [Algorithm] 그리디
2023.03.06그리디 알고리즘(Greedy) 가장 단순하지만 강력한 문제 해결 방법이다. '탐욕법'이라고 불리기도 한다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 다익스트라, 플로이드 워셜 알고리즘은 엄밀히 말하자면, 그리디 알고리즘으로 분류된다. 그리디 알고리즘 유형은 매우 다양하기 때문에, 특이 케이스를 제외하고는 단순 암기를 통해 해결할 수 있는 알고리즘 유형이 아니다. 따라서 많은 유형의 그리디 알고리즘 유형을 접해봐야한다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로, '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준을 본인이 직접 정해줘야한다. ex) 예시를 통해 그리디 알고리즘을 이해해보자. 위의 문제는 그리디 알고리..
Algorithm과 Problem Solving
Algorithm과 Problem Solving
2023.02.25Algorithm과 Problem Solving (feat.이코테) 동일한 기능을 구현함에 있어서 주어진 조건에 따라서 효율적인 로직이 무엇일까를 고민해 보는 과정은, "나 자신과의 싸움의 연속이었다." "이것이 취업을 위한 코딩 테스트다"라는 책을 통해 처음 알고리즘 공부에 입문하게 되었고, 해당 도서의 필자가 추천한 로드맵을 따라 한 걸음씩 정진했다. 시간이 좀 오래 걸렸지만, 책을 완독했고, 이 책에서 제시하는 주요 알고리즘 이론과 실전 문제에 어느 정도 익숙해진듯하다. 그리디 구현 DFS/BFS 정렬(선택, 삽입, 퀵, 계수) 이진 탐색 다이나믹 프로그래밍 최단 경로(다익스트라, 플로이드 워셜) 그래프 이론(신장 트리, 위상 정렬) 이론에 대한 실전문제를 바로바로 풀어보려고 노력했으며, 백준(ht..