철갑이의 이모저모

문제 programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 풀이 각각의 수포자들 패턴과 답안을 비교해서 카운트 enumerate() 함수를 이용해 인덱스 값을 받아 출력한다. 답 def solution(answers): no_1 = [1, 2, 3, 4, 5] no_2 = [2, 1, 2, 3, 2, 4, 2, 5] no_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] cnt = [0, 0, 0] for i in ..

문제 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 동전의 갯수가 최솟값을 가져야 하기 때문에 큰 수 부터 나눠준다. 동전의 가치가 오름차순으로 입력이 되기 때문에 coin[::-1](리스트 역으로 출력) 사용, pop() 으로 작성해도 된다. 1. k원을 동전의 가치로 나눠주고(몫만 필요하기 때문에 // 사용) 2. k원에서 (1에서 나온 몫 * 동전의 가치)를 빼준 후 3. 코인 개수..

문제 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 먼저 LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 부분을 말한다. 예시로 ACAYKP와 CAPCAK를 이용해 표를 그려보았다. ACAYKP를 비교 대상으로 잡고 CAPCAK 문자열 하나씩 추가하면서 공통 수열 길이 값을 표시해준다. 위와 같이 반복을 하..

문제 www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 풀이 2630번 색종이 만들기 문제와 같은 유형이다. www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [백준] 2630..

문제 www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할 정복 : 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식 첫 색상이 나머지 색상과 같은지 확인 후 틀린 것이 있으면, 틀린 구역을 다시 네 구역으로 나누어 다시 색상이 같은 것을 확인해주기 위해 재귀를 이용해서 풀었다. 재귀 호출시 들어가야하는 인수의 값이 헷갈려서 그림으로 시작점을 표시해보았다. 비슷한 문제 [백준] 1992번(쿼드트리) with ..

문제 www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 배열을 정렬한 후 itertools 라이브러리에서 combinations 이터레이터를 사용해서 문제를 풀었다. 그리고 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성이 되었는지 카운트 해서 결과를 도출했다. docs.python.org/ko/3/library/itertools.html#itertools.combinations itertools — 효율적인 루핑을 위한 이터레이터..

Queue(큐) 큐(Queue)는 뒤(rear)에서 데이터를 넣고(enqueue), 앞(front)에서 데이터를 꺼내는(dequeue)는 선형 자료구조 이다. FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과는 반대되는 개념. 줄을 서는 행위를 생각하면 이해가 쉽다. 프린터의 출력, 운영체제의 프로세스 관리에서 데이터나 작업이 입력된 순서대로 처리해야할 때 응용되는 구조이다. (멀티태스킹을 위한 프로세스 스케쥴링 방식) Python 에서의 Queue 라이브러리 # Queue() 일반적인 큐(FIFO) import queue q = queue.Queue() # 큐에 데이터를 넣을때 put 사용 q.put("first") q.put("second"..

문제 www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 풀이 비슷한 문제 [백준] 11727번(2xn 타일링 2) with Python 문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. w.. happylsm76.tistory.com 다른 점이라면 예제를 입력 받는 부분을 어떻게 처리해야하나 고민했다. www.acmicpc.net..

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다. 위의 그림과 같이 N이 3 이상 이면 N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다. 따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2 dp[1]과 dp[2]를 미리 구해서 시작. 답 a = int(input()) dp = [0,1,3] for i in range(3, a + ..

10/06 Talk about marathon clubs In the past I thought marathon were all about running on and on. But after I joined the club for marathoners and I tried myself I realized that marathons are a lot like our lives in many ways. The ultimate goal is to run the full course of 42.195km. There are also 21km half marathons and 10k races. Runners might slow down their pace if they get too tired half way ..