출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 27, p 367 재귀함수로 구현한 이진 탐색 코드를 참고하여 풀이했습니다. 타겟 값이 있는 인덱스를 result라는 집합에 모두 추가하고 이 집합의 길이를 반환했습니다. 기존의 이진 탐색과 동일하지만, 중간값이 타겟과 같은 경우 현재 중간값을 result 집합에 추가해주었고, 왼쪽과 오른쪽 모두에 타겟이 더 있을 수 있으므로 end를 mid-1로 갱신한 탐색, start를 mid+1로 갱신한 탐색 모두를 진행하도록 했습니다. 타겟 원소가 하나도 없으면 -1을 출력하도록 했으므로 result의 길이가 0보다 크면 len(result)를, 그렇지 않으면 -1을 출력하도록 했습니다. https://codlingual.tistory.com/189 ..

이진 탐색의 시간 복잡도: O(logN) 정렬되지 않은 길이 N의 리스트에서 M개의 값을 이진 탐색으로 찾을 때 시간 복잡도: O((M+N)*logN) 길이 N의 리스트 정렬하기: O(N*logN) 정렬된 길이 N의 리스트에서 M번 이진 탐색하기: O(M*longN) 1. 재귀 함수로 구현한 이진 탐색 코드 # 이진 탐색 소스코드 구현(재귀 함수) 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]..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 입력을 받아와 인접 리스트로 바꿔주고, 이를 다시 list of list로 변환하는데, 이때 i번째 리스트에는 i번째 컴퓨터와 직접 연결되어 있는 컴퓨터들의 번호가 저장됩니다. 이를 이용해 시작점을 1로 하고 dfs 함수를 수행해줍니다. visited 리스트 중 1번 컴퓨터를 제외한 컴퓨터들의 개수를 sum을 이용해 구한 후 반환합니다. https://codlingual.tistory.com/182 D..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr DFS를 수행하는 함수 dfs를 정의하고, 모든 컴퓨터를 방문할 때까지 dfs를 반복합니다. 우선 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문합니다. 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출합니다. 모든 ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리 구조를 TreeNode라는 클래스로, 리스트를 입력으로 받아 트리 구조로 만들어주는 함수 makeTree를 정의했습니다. 우선 입력을 받아와 노드의 개수 N을 제외하고 3개씩 묶어 nodes라는 리스트에 저장합니다. 이후 makeTree 함수를 이용해 트리 구조로 바꿔줍니다. 트리 구조로 바꿔준 input을 순서대로 전위순회 preorder, 중위순회 inorder, 후위순회 posto..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net RotatingQueue라는 클래스를 정의하여 문제에 주어진 연산1,2,3을 구현했습니다. 뽑아야 하는 숫자들의 리스트를 targets로 정의하고, 이 숫자들을 하나씩 뽑으면서 현재 큐의 첫 번째 원소면 count 증가 없이 바로 연산1 수행, 앞쪽에 있으면 첫 번째 원소가 될 때까지 연산2를 수행하고, 수행한 횟수만큼 count 증가, 뒷쪽에 있으면 첫 번째 원소가 될 때까지 연산3을 수행하..