Berom's Blog

이분 탐색이란(What is binary Search)이분 탐색은 __정렬된 배열__에서 중앙값과 비교하여 목표값을 찾는 알고리즘이다. 목표 값을 중앙값(Mid)과 비교하여,중앙값보다 목표값이 작거나 크다면 범위를 중앙 값 기준으로 범위를 절반 제한하며 탐색한다. 길이 15이고, 인덱스와 배열의 값이 같은 배열에서 이분 탐색을 하는 상황을 가정해보자(편의상 배열의 중앙 값은 Mid, 시작은 start, 끝은 end다.)start의 인덱스는 0, end는 14이다. Mid는 (0+14)2인 7이다. 우리가 찾고 싶은 값은 3이다.3은 mid 7보다 작으므로, 중앙값 기준으로 왼쪽에 있으며, 중앙 값의 오른편은 값이 없음을 신뢰할 수 있다.이 때 왼 편을 기준으로 다시 이분 탐색을 한다.start는 0,end는 (mid-1)인 6, 새로운 mid는 (0+6)/3이다.그 후 다시 3을 찾을 때까지 이분 탐색을 반복한다. 이분 탐색의 핵심은 중앙 값을 이용해 검색 범위를 줄여나가 ...

백준 1003 피보나치 함수문제피보나치 수열의 0과 1의 갯수를 구해서 출력하는 문제이다 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. 출력각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 풀이12345678910111213import sys# fibo(n) = fibo(n-2) + fibo(n-1)zdp = [1,0]odp = [0,1]for i in range(2,41): zdp.append(zdp[i-2]+zdp[i-1]) odp.append(odp[i-2]+odp[i-1])n = int(sys.stdin.readline())for j in range(n): num = int(sys.stdin.readline()) print(f"{zdp[num]} {odp[num]
...

백준 1012 유기농 배추문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다 ...

백준 1074 Z문제한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 풀이12345678910111213141516171819202122import sysN,r,c = map(int,sys.stdin.readline().split())ans = 0while N!=0: N-=1 if r<2**N and c<2**N: continue elif r<2**N and c>=2**N: ans +=(2**N)*(2**N)*1 c-=(2**N) elif r>=2 **N and c<2 ...

백준 10820 문자열 분석문제문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다. 입력첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열의 길이는 100을 넘지 않는다. 출력첫째 줄부터 N번째 줄까지 각각의 문자열에 대해서 소문자, 대문자, 숫자, 공백의 개수를 공백으로 구분해 출력한다. 풀이대소문자,공백, 숫자를 카운트하는건 어렵지 않았다. EOF 처리랑 문자열을 어떻게 만질것인가가 관건이다. 문제 풀 때 rstrip()을 무심코 사용했었는데 그래서 틀릴 뻔 했다. rstrip()rstrip()은 인자로 주어지는 문자를 문자열에서 모두 지우는 메소드이다.기본적으로 아무것도 주어지지 않으면 문자열의 끝(개행문자)와 공백을 지운다. 핵심 아이디어 EOF 처리를 어떻게 할 것인가? 문자열이 얼마나 들어올지 알려주 ...

동전 0문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 풀이123456789101112131415import sysn,k = map(int,sys.stdin.readline().split())coins=[int(sys.stdin.readline()) for i in range(n)]cnt=0for i in range(n-1,-1,-1): if k==0: break if coins[i]>k: continue cnt+=k//coins[i] k%=coins[i]print(cnt)

백준 11279 최대 힙문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 풀이12345678910111213141516171819import sysimport heapq# 배열에 자연수를 x를 넣는다# 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거한다n = int(sys.stdin.readline())l = []for i in range(n): t= int(sys.stdin.readline()) if t == 0: if not l: print(0) else: print(heapq.heappop(l)[1]) else: heapq.heappush(l, (-t,t)) 파이썬의 ...

백준 11286 절댓값 힙문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다. 풀이1234567891011121314import sysimport heapqn = int(sys.stdin.readline())heap=[]for i in range(n): num=int(sys.stdin.readline()) if num ==0: if not heap: print(0) continue print(heap ...

백준 11403 경로 찾기문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다 풀이12345678910111213141516171819202122232425262728293031323334import sysfrom collections import dequen = int(sys.stdin.readline())mp=[list(map(int,s ...

백준 1149 RGB 거리문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 풀이코드1234567891011121314import sysn = int(sys.stdin.readline())dp = [[0]*3 for i in range(n)]numbers=[]for i in range(n): numbers.append(list(map(int,sys.stdin.readline().split())))dp[0]=numbers[0]for i in r ...