이진탐색 이진탐색이란 반으로 쪼개가면서 탐색하는 것이다. 이진탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있고, 단, 배열 내부의 데이터가 정렬되어 있어야하며 위치를 나타내는 변수 3개를 사용하는데 "시작점, 끝점, 중간점"을 사용한다. 핵심은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다. 이진탐색은 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도가 O(logN)이다. 이진탐색을 구현하는 방법에는 두가지가 있다. 1. 재귀함수 2. 반복문 # 재귀함수 코드 def binary_search(array,target,start,end): if start > end : return None mid = (start+end)//..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 처음 딱 접했을 때 문제는 "이것이 취업을 위한 코딩테스트다"에 실린 음료수얼려먹기 문제와 유사했다. 하지만 조금 다른 점이 있다. 핵심 1. 덩어리 개수를 구할 것 2. 상하좌우로 움직일 수 있을 뿐만 아니라 대각선 방향으로도 움직일 수 있다. 음료수얼려먹기 문제가 dfs로 풀려서 나도 dfs로 처음에 구현했다. 근데 여론을 보니 dfs와 bfs 모두 가능하다고 한다. 따라서 두가지 방법으..

www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이법 1) 소인수분해하는 코드 num = int(sys.stdin.readline()) su = 2 # 검사할 첫 값 so = [] # 소인수 저장할 리스트 변수 while su collections 라이브러리의 Counter 함수 사용하여 dictionary 형태로 값을 받고 반복문으로 출력한다. dict = collections.Counter(so) for key in dict: print(key, dict[key]) 참고자료 1. 소인수분해 blog.daum.net/s..

www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 최소공배수 구하는 문제이다 라이브러리를 사용하면 쉽게 풀 수 있는 문제다 from math import gcd def lcm(x,y): return x*y // gcd(x,y) # 최대공약수 n = int(input()) for _ in range(n): a,b = map(int,input().split()) print(lcm(a,b)) brownbears.tistory.com/454 [Python] 최대공약수, 최소공배수, N개의 최소..

www.acmicpc.net/problem/2010 2010번: 플러그 첫째 줄에 멀티탭의 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연 www.acmicpc.net 입력을 input() 으로 받으면 시간초과가 난다. 따라서 입력을 sys.stdin.readline()

www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 30의 배수이려면 1) 일의 자리수가 무조건 0이어야함 2) 각 자리수의 합이 3으로 나누어 떨어져야함 n = list(input()) n.sort(reverse=True) sum =0 for i in n: sum += int(i) if sum%3!=0 or "0" not in n: print(-1) else: print("".join(n)) 새로운 개념) n = list(input()) 입력받은 문자열을 한자리..