최신 글
-
Python 코딩테스트
DP(다이나믹 프로그래밍): 백준 11726 파이썬
문제: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이: 이 문제는 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다. 이 문제에서도 10007로 나눈 나머지를 출력하라고 하는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다. 왼쪽부터 차례..
-
Python 코딩테스트
DP(다이나믹 프로그래밍): 백준 9095 파이썬 1,2,3 더하기
문제: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이: 이 문제를 풀면서 어떻게 점화식을 세워야 하는지에 대한 고민을 1시간 정도 했었는데 잘 떠오르지 않아 결국 구글링을 했다. 규칙은 아주 간단했다. 점화식을 찾아서 해결하는 전형적인 DP문제였다. 1 -> (1), 1개 2 -> (1+1), (2) 2개 3 -> (1+1+1), (1+2), (2+1), (3) 4개 4 -> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), .... 7개 5 -> (1+1+1+1+1), .... 13개 위의 규칙을 봤을 때, 정수 4..
-
Python 코딩테스트
[프로그래머스] 파일명 정렬 파이썬
문제: https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이: 알고리즘은 아래와 같다. 1. head, number, tail로 분리 2. sorted의 lambda로 다중 정렬 기준 주기 3. 비교시에 head의 경우 대소문자 구분 없는 것으로 비교하고 출력 때는 원래 것, number도 마찬가지로 비교는 숫자로 바꿔서 비교하고 출력할 때는 다시 원래 것 (문자열)로 해야 하기 때문에 튜플로 묶어서 저장한다. 4. 비교시에는 튜플의 1번째 원..
-
Python 코딩테스트
BFS: 백준 13549 숨바꼭질 3
문제: https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이: 1697번 문제 숨바꼭질 1에서 순간이동을 하는 경우엔 1의 가중치가 없어지도록 한 문제이다. x+1, x-1, x*2 로 이동하는 경우를 각각 처리해주어야 한다. 만약 순간이동할 경우 큐의 맨 앞에 순간이동한 후의 좌표를 추가 해주어 연산에 우선순위를 주어야 한다. 이렇게 하면 각 좌표로 이동하는 최단시간이 dist 배열에 저장된다. 정답: imp..
-
Python 코딩테스트
[프로그래머스] 튜플 파이썬
문제: https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이: 입력받은 s를 리스트로 변환한다. 그 이후에는 만들어진 리스트의 요소를 하나씩 접근, answer 리스트에 중복이 되지 않도록 not in 을 사용하여 하나 씩 append 한다. 여기서 핵심은 {{2}, {2,1}, {2,1,3}, {2,1,3,4}} {{2,1,3,4}, {2}, {2,1,3}, {2,1}} {{1,2,3}, {2,1}, {1,2,4,3}, {2}} 일 경우 다 ..
-
Python 코딩테스트
그리디: 백준 1931 파이썬 회의실 배정
문제: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이: 이 문제는 정렬을 해야 한다는 아이디어를 생각해내면 풀 수 있는 문제이다. sort()함수의 key값을 사용해 회의실 사용이 끝나는 시간을 기준으로 먼저 정렬하고 끝나는 시간이 같다면 시작시간을 기준으로 정렬되게 한다. 그리고 회의실 사용이 끝나는 시간과 다른 회의의 시작시간을 비교해 카운트를 하면 된다. 정답: import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in ra..
-
Python 코딩테스트
DP(다이나믹 프로그래밍): 백준 15988 파이썬 1,2,3 더하기 3
문제: https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이: 이 문제는 '1,2,3, 더하기 1' 9095번 문제에서 n의 범위가 크게 늘어난 문제이다. 이 문제에 9095번 문제와 같은 코드를 제출하면 메모리 초과가 발생한다. 그래서 다르게 풀어야 하는데, 먼저 다이나믹 프로그래밍 기법으로 범위 내의 방법 수를 다 구해서 리스트 'd'에 모두 저장한 뒤에 각 테스트 케이스를 입력받아 리스트 'arr'에 그 결과를 저장한다. 입력받은 테스트 케이스를 모두 저장하고 있지 않고, 테스트 케이스에 ..
