Coder's Cattitude

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제를 딱 보면 끝이 0인 애들은 뒤에 0이나 1이 올 수 있고, 끝이 1인 애들은 0밖에 못오는 것을 알 수 있다. 그래서 생각한게 0으로 끝나는 수와 1로 끝나는 수들의 개수를 따로 저장하는 것이었다. 그래서 1차원 배열이 아닌 2차원 배열로 dp를 만들어서 끝이 0인 수의 개수는 0열에, 끝이 1인 수의 개수는 1열에 저장하기로 한다. n 0으로 끝나는 수 1로 끝나는 수 1 - 1 2 10 - 3 100 101 4 1010, 1000 1001 5 10100, 100000, 10010 10101, 100001 위의 표를 개수로 나타내 보겠다 n 0으로 끝나는 수들의 개수 1로 끝나는 수들의 개수 1 0 1 2 1 0 3 1 1 4 2 1 5 3 2 .....

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 위의 그림을 보면 n이 1이고, 2인 경우를 제외하면 n이 3부터는 규칙이 생기는 것을 알 수 있다. 2 x n을 만들기 위해서는 2가지 방법이 있다. 2 x (n - 1) 인 경우에 1 x 2 타일 1개 붙이기 2 x (n - 2) 인 경우에 2 x 2 타일이나 2 x 1 타일 2개 붙이기 그래서 식으로 적으면 dp[n] = dp[n - 1] + dp[n - 2] * 2가 된다. 위의 그림을 보면 이해가 더 쉬울 것이다. 분홍색 형광펜으로 네모 표시를 한 부분들이 바로 이전 타일들에 추가된 부분들이다. 아래는 dp 식을 정리한 것이다. dp를 위한 배열을 만들 때, n이 아닌, n + 1 배열로 만드는 것이 편하다. 🔑 python 코드 # 2xN 타일링 2..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 📌 풀이 문제에서 주어진 숫자 S를 서로 다른 자연수들을 N개 더해서 만드는데 N의 개수의 최댓값을 구하는 것이다. 쉽게 생각하면 작은 수인 1부터 2, 3,,, 차례로 더해가면 N이 최대가 된다 는 것을 생각하면 된다. 그래서 생각해낸 풀이 방법이 등차가 1인 등차 수열을 생각해서 등차수열의 합 공식을 사용하는 것이었다. temp = 1 + 2 + 3 +,,, + n까지 더한 값은 temp = n * (n + 1) / 2 로 구할 수 있다. 이 temp 값이 S값 커졌을 때의 n 값에서 1을 뺀 것이 바로 답이다. 1을 빼주는 이유는 200을 예를 들어서 설명하겠다 200에 가장 가까운 200보다 큰 temp 값은 n이 20인 210이다. temp가 210일 때 n값..

🔒 문제 ⌨ 입력 🖨 출력 📍 제한 📚 예제 📌 풀이 🔑 python 코드 # Z import sys input = sys.stdin.readline N, r, c = map(int, input().split()) visit = 0 while(N > 0): N -= 1 size = 2 ** N # 1사분면 if r = size: visit += size*size c -= size # 3사분면 elif r >= size and c < size: visit += size * size * 2 r -= size # 4사분면 else: visit += size * size * 3 r -= size c -= ..

🔒 문제 1 : 부품 찾기 도깡이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 도깡이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력한다. 구분은 공백으로 한다. ⌨..

1. 순차 탐색 (Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다. 즉 리스트 내에 데이터가 아무리 많아도 충분한 시간만 존재한다면, 항상 원하는 데이터(원소)를 찾을 수 있다는 장점이 있다. Ex) 순차 탐색으로 &#39;도깡이&#39; 찾기 step 0️⃣ : 초기 단계 step 1️⃣ : 가장 먼저 첫 번째 데이터를 확인한다. &#39;가을이&#39;는 찾고자 하는 문자열과 같지 않다. 따라서 다음 데이터로 이동한다. step 2️⃣ : 두 번째 데이터를 확인한다. &#39;초코&#39;는 찾고자 하는 문자열과 같지 않다. 따라서 다음 데이터로 이동한다. step..

5. 파이썬 정렬 라이브러리 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted() 함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다. 병합 정렬은 일반적으로 퀵 정렬보다 느리지만, 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. 이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 물론 집합이나 딕셔너리 자료형을 입력받아도 return 값은 리스트이다. 1) sorted.py array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] result = sorted(array) print(result) - 출력 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 2) sort.py..

4. 계수 정렬 (Count sort) 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘 이다. 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O ( N + K)를 보장한다. 계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라, 원리 또한 매우 간단하다. 다만 계수정렬은 &#39;데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때&#39; 만 사용할 수 있다. 예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 할 수 ..

🔒 문제 ⌨ 입력 🖨 출력 📚 예제 예외 ex1) 1 131 -1 ex2) 1 1111 5 📌 풀이 문제를 찬찬히 보면 A -> B를 만든다기보다는 B -> A를 만드는 것이 쉽다. 그래서 규칙을 찾아보면, [규칙] B의 일의 자리 수가 1이면, B에 B를 10으로 나눈 몫을 저장한다. B를 2로 나누었을 때 나머지가 0이면, B에 B를 2로 나눈 몫을 저장한다. 3. B를 2로 나누었을 때 나머지가 0이 아니면, ans에 -1을 저장하고 ans를 출력한다. while문을 탈출하는 방법은 3개이다. 3번 조건을 생각안해서 틀렸었다 [while문 탈출] A와 B가 같아졌을 때 B가 A보다 작아졌을 때 A로 B를 만들 수 없을 때 2번, 3번은 답이 -1이다. 🔑 python 코드 # A -> B impor..

3. 퀵 정렬 퀵 정렬은 지금까지 배운 정렬 알고리즘 중 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 &#39;병합 정렬&#39; 알고리즘이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬이 어떻게 동작하기에 이름부터 &#39;빠른 정렬 알고리즘&#39;일까? &#39;기준 데이터를 성정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?&#39; 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 &#39;피벗(pivot)&#39; 이 사용된다. 큰 수와 작은 수를 교환할 때, 교환하기 위한 &#39;기준&#39; 이 바로 &#39;피..