분류 전체보기(54)
-
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 5강(이진 탐색 알고리즘)
이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: retu..
2021.05.02 -
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 4-2강(계수 정렬, 예제)
계수 정렬 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다. # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 for i in r..
2021.05.02 -
kaggle , [Tabular Playground Series - Apr 2021]
캐글에서 열린 [Tabular Playground Series - Apr 2021]대회에 참가했다. www.kaggle.com/c/tabular-playground-series-apr-2021 'The dataset is used for this competition is synthetic but based on a real dataset (in this case, the actual Titanic data!) and generated using a CTGAN. The statistical properties of this dataset are very similar to the original Titanic dataset, but there's no way to "cheat" by using publi..
2021.05.01 -
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 4-1강(정렬 알고리즘:선택 정렬, 삽입 정렬, 퀵 정렬)
정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 데이터의 개수가 적을 때 , 한정되어 있을 때 등 다양한 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): # i는 가장 작은 데이터와 위치가 바뀐 인덱스를 말한다 = 앞쪽 원소의 위치 min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_inde..
2021.05.01 -
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 3-2강(DFS , BFS, 음료수 얼려먹기, 미로 탈출)
DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end = '') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in g..
2021.05.01 -
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 3-1강(스택, 큐, 재귀 함수)
그래프 탐색 알고리즘 : DFS/BFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 위의 그림과는 반대방향으로 이루어진다. 코드상으로는 오른쪽으로 원소가 들어와 popleft 를 사용하면 왼쪽부터 원소가 삭제된다. 큐를 구현할 때는 list형태가 아닌 deque 라이브러리를 사용해야 시간적으로 우수하다.
2021.04.30