min's devlog min's devlog

🎈 백준 2470 두 용액 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. => 범위를 생각하면 완전탐색으로 풀 수 없다. • 산성 용액(양의 정수 값), 알칼리성 용액(음의 정수 값) 중 두 용액을 혼합한다. => 같은 종..

🎈 kakao 60060 가사 검색 programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr ❗ 문제의 핵심, 풀이 과정 • '?'는 글자 하나를 의미한다. => 예를 들어, "fro??" 는 길이가 5인 단어이며, 길이가 5인 단어리스트에서 찾는 것이 효율적이다. => 모든 단어들이 담긴 배열 words에서 각 단어들을 길이별로 구분하여 저장한다. • 와일드카드 문자인 '?'는 반드시 하나 이상 포함되어있으며, 검색 키워드의 접두사 아니면 접미사이다. => 접두사인 경우 단어를 뒤집어서 저장한다. -> reversed_arr 이용 • 모든 단어들이 담긴 배열 words에서 키워드가 담긴 배열 queries의 키..

🎈 백준 2110 공유기 설치 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개..

이진 탐색 (Binary Search) 데이터가 정렬되어있을 때, 탐색 범위를 반으로 줄여가며 데이터를 빠르게 탐색하는 방법이다. - 시작점, 끝점, 중간점을 이용한다. - 중간점을 이용해서 탐색 범위를 줄여나간다. • 재귀 함수로 구현한 이진 탐색 소스코드 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 인덱스 반환 if arr[mid] == target: return mid # 중간값보다 target이 작은 경우 왼쪽 부분 확인 elif arr[mid] > target: return binary_search(arr, target, start, mid - 1) # ..

파이썬의 정렬 라이브러리 sort() 기본 정렬 라이브러리 sort() 함수를 제공한다. sort() : 병합정렬 기반으로, 퀵 정렬보단 느리지만 O(nlogn)을 보장한다. list.sort() : 리스트 내에서 정렬한다. (여기서 list는 직접 수정이 가능하다.) sorted(list) : 새로운 정렬 리스트를 생성한다. (여기서 list는 튜플, 딕셔너리, 문자열 등이다.) reverse 리스트 뒤집기 # 내림차순 arr.sort(reverse=True) *sorted(arr, reverse=True) key, lambda s = ['가', '나다', '라', '마바아자', '차카파'] s.sort(key=len) # len에 따라 정렬 print(*sorted(arr, key=lambda x:(..

정렬 (Sorting) 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 선택 정렬(Selection Sort) 정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트를 가정하고, 오른쪽 리스트에서 최소값을 선택하여 오른쪽 리스트의 첫번째 수와 교환한다. • 선택 정렬의 소스코드 arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(arr)): if arr[min_index] > arr[j]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] # 교환 print(arr) • 선택 정렬의..

🎈 백준 2580 스도쿠 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 ..

🎈 백준 2579 계단 오르기 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 ..