꾸준함의 기록

백준 1300번 K번째 수 파이썬 풀이 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 정답코드 # K번째 수 N = int(input()) K = int(input()) def Binary(start, end): while start = K: # 줄여야하므로 end = mid - 1 else: # 키워야 하므로 start = mid + 1 return start print(Binary(1, 10**9)) 풀이과정 Q) 왜 return end 가 아니라 return start인가? start 는 ..

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 정답코드 # 공유기 설치 from array import array import sys N,C = map(int,input().split()) answer = 0 location_list = [] ..

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다..

이진 탐색 알고리즘에 대해 알아보자 이진 탐색(binary search) ● 정의 - 정렬되어 있는 리스트에서 탐색 범위를 절반으로 좁혀가며 데이터를 탐색하는 방법 ● 특징 1. 배열의 내부 데이터가 정렬되어 있어야만 사용 가능 2. 변수 3개(start, end, mid)를 사용하여 탐색. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복 비교하며 원하는 데이터를 찾는다. 3. 시간복잡도가 O(log N) 이다. ● 구현 코드 (Python) # 이분탐색 array = [4,3,5,1,2,6] # 정렬되지 않은 배열 array = sorted(array) # sorted 로 정렬하기 print("array:",array) def binary_search(array, target, start, end)..

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 정답코드 #AC from collections import deque import sys T..

1. 짝수 홀수 분기 처리 시 //이 아니라, %을 사용하기 def recursive(matrix,n): if n == 1: return matrix #elif n // 2 == 0: elif n % 2 == 0: matrix = recursive(matrix, n//2) return multi(matrix, matrix) else: matrix = recursive(matrix, n-1) return multi(matrix, initial_matrix) 2. 호출 두번 -호출코드를 엄청 밑에다 적어둬서 보이지 않았음.. #index 이므로 BFS(start_point[0] - 1, start_point[1] - 1, start_point[2]) #index 는 0으로 시작하므로 - 1 BFS(start..

백준 11401번 이항계수3 파이썬 풀이 문제 자연수 n과 정수 k가 주어졌을 때 이항 계수 nCk를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 선제적으로 알고 있어야하는 개념 역원 그 수와 곱하면 곱셈 항등원(1)이 되는 수 모듈로 연산(Modulo Operation) 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. ex) 18 (mod 5) = 3 ex) 7²²² mod 11 계산하기 7¹¹-¹ = 1(mod 11) 7¹⁰ = 1(mod 11) 7²²² = 7²²*¹⁰ x 7² (mod 11) = 49(mod 11) = 5(mod 11) 페르마의 소정리 여기 p가 소수이고 a가 정수라고 할 때 p에서 a^p와 a는 서로 합동이..

백준 17298 오큰수 파이썬 풀이 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 정답코드 #오큰수 N = int(input()) arr = list(map(int,input().split())) result =..

백준 4949 균형잡힌 세상 파이썬 풀이 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 ..

백준 1707번 이분 그래프 파이썬 풀이 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 이분그래프란? 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는( 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 함. (청팀 백팀 같은 느낌??) 정답코드 #이분 그래프 import s..