파이썬

이진 탐색 알고리즘

이진 탐색(Binary Search) 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 시간 복잡도는 $O(logn)$을 가진다. ✔ 이진 탐색 과정 1. 데이터 집합(배열)의 중앙 요소를 선택합니다. 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 여기서 target = 9 로 한다. 2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다. 다시 구한 중앙값은 10이다. 3. 위의 2번을..

[이것이 코딩 테스트다 with Python] 성적이 낮은 순서로 학생 출력하기

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 6 정렬 실전문제 6-2 위에서 아래로 180p 문제 N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다. 입력 조건 첫 번째 줄에 학생의 수 N이 입력된다. (1

[그래프 탐색] DFS, BFS 문제

공통 문제 graph의 노드당 인접 노드가 배열로 주어질 때 방문 순서 프린트 하기 DFS 코드 def dfs(graph, v, visited): visited[v]=True # 현재 node visited 체크하기 print(v, end=' ') # 방문 위치 print for i in graph[v]: # 그래프 연결된 위치에 대해서 방문되지 않은 곳 있으면 dfs 호출하기 if not visited[i]: dfs(graph,i,visited) # 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트) graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]] # 각 노드가 방문된 정보를 리스트 자료형..

[이것이 코딩 테스트다 with Python] 그리디 : 숫자 카드 게임

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-3 숫자 카드 게임 96p 문제 설명 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 단, 게임의 룰을 지키며 뽑아야함 숫자가 쓰인 카드들이 N X M 형태로 놓여 있습니다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미합니다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 합니다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인..