-
알고리즘
[코테] # 6. 이진 탐색
동빈나의 이코테 강의를 듣고 작성한 포스트입니다. 이진 탐색은 리스트 내에서 데이터의 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 순차 탐색가장 기본 탐색 방법인 순차 탐색은, 리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서부터 데이터를 하나씩 차례로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다.데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인한다.데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시각 복잡도는 O(N)이다. 이진 탐색배열의 데이터가 정렬되어 있어야만 이진 탐색을 사용할 수 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.이진 탐색은 위치를 나타내는 변수 3개를 사..
-
알고리즘
[BOJ](Python) 백준 9466번: 텀 프로젝트
문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 주제 방향 그래프 & DFS 시간 / 메모리 제한 3초 / 256MB 정답 비율 24.043% 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행한다. 프로젝트 팀원 수에는 제한이 없다. 모든 학생들이 동일한 팀의 팀원인 경우처럼 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택한다. 각자 단 한 명만 선택할 수 있다...
-
알고리즘
[BOJ](Python) 백준 5567번: 결혼식
문제 https://acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 주제 그래프 구현/순회 시간 / 메모리 제한 1초 / 128MB 정답 비율 44.052% 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 갖고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 ..
-
알고리즘
[BOJ](Python) 백준 1920번: 수 찾기
문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 주제 해시 테이블 시간 / 메모리 제한 1초 / 128MB 정답 비율 29.789% N개의 정수 A[1], A[2], ... , A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1
-
알고리즘
[BOJ](Python) 백준 1620번: 나는야 포켓몬 마스터 이다솜
문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 주제 이진 탐색 시간 / 메모리 제한 2초 / 256MB 정답 비율 34.067% 입력 첫째 줄에는 도감에 수록된 포켓몬의 개수 N과 내가 맞춰야 하는 문제의 개수 M이 주어진다. 1 target: return binary_search(dic, target, start, mid - 1) else: return binary_search(dic, target, mid..
