출처 : 백준, https://www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. DP 불변의 법칙 이전 단계를 생각하자. 풀이 n, m = map(int, input().split()) map = [[1 for _ in range(m)] for _ in range(n)] for i in range(1, n): for j in range(1, m): map[i][j] = (map[i-1][j] + map[i-1][j-1] +..
출처 : 백준, https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. DP 문제이다. 규칙을 찾기 위해 한 단계 거슬러가서 생각해보자. 풀이 n = int(input()) FIRST_START = 1 LAST_START = 2 winner = [FIRST_START for _ in range(n+1)] try: winner[2] = LAST_START except: pass for i in range(5, n+1): if LAST_START in [winner[i-4], winner[i-3], winner[i-1]]: winner..
출처 : 백준, https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 나눗셈 연산은 부동소수점 에러를 일으킬 수 있다. 풀이 n, k = map(int, input().split()) dp = [1 for _ in range(n+1)] for i in range(1, n+1): dp[i] = (dp[i-1] * i) print((dp[n] // (dp[n-k] * dp[k])) % 10007) 그냥 팩토리얼을 쭉 구해서 조합 계산식을 돌리는 풀이이다. 마지막에 / 연산 시행 시, 나..
출처 : 백준 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 전형적인 DP 문제이다. DP는 최솟값, 최댓값을 찾거나 혹은 특정 조건을 만족하는 해의 개수를 찾을 때 주료 사용되는데, 이 문제는 특정 조건을 만족하는 해의 개수를 찾는 Counting 문제이다. DP에서 규칙을 찾아내기 좋은 방법은, 바로 한 단계 전을 생각하는 것. n번째 블록에서 블록이 추가되기 전을 생각하며 규칙을 찾아보자. 풀이 n = int(input()) dp..
출처 : 백준, https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 전형적인 DP 문제인데 해보면 규칙이 나오는 경우......... 풀이 T = int(input()) for _ in range(T): n = int(input()) dp = [[0 for _ in range(n+1)] for _ in range(2)] try: dp[0][0] = 1 dp[1][1] = 1 except: pass for i in range(2, n+1): dp[0][i] = dp[0][i-1] + dp[0][i-2] dp[..
출처 : 백준, https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 딱히 없지만, 알아두면 좋을 것이 이 문제는 2가지 방식으로 풀 수 있다. 문제를 풀고 자신이 문제를 푼 방식과 다른 방식으로도 한 번 더 풀어보자. 풀이1 : Greedy n = int(input()) a = n // 5 while True: if a < 0: print(-1) break new_N = n - a * 5 if new_N % 3 == 0:..
출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 더보기 먼저, 생각해야 할 부분 1. 이전 것이 무조건 전에 포함되어야한다. 단순히 스킬 트리 상에 존재하는 것이 스킬 순서만 지키면 되는게 아니라 CBD에서 B가 포함될 경우 C도 존재하여야 한다. 풀이 def solution(skill, skill_trees): skill_set = set([char for char in skill]) count = 0 for tree in skill_trees: order = ''.join([char for char in tree if char in skill_set]) if ski..
깃허브를 사용하면서 기능별로 feature 브랜치를 파고 PR을 올리고 머지한 적은 있지만, 브랜치 명칭별로 어떤 역할을 하는지, 어떻게 관리되어야하는지에 대해서는 깊게 생각해본 적이 없었다. 오늘 인턴쉽을 진행하며 배웠던 깃 플로우 전략을 아주아주 간단하게 정리해두려고 한다. 브랜치의 종류는 5가지가 있다. develop 개발이 진행 중인 branch feature 특정 기능의 개발이 진행되는 branch release 기능 개발이 끝나고, 제품 출시 전 테스팅용 DB와 서버에서 빌드되어 QA 과정에 놓이는 branch master 빌드 되어 실제 배포되는 branch hotfix 배포된 결과물에서 발생한 문제를 빠르게 해결하기 위한 branch 실제 개발과정에서는 위 브랜치를 다음과 같이 적용한다. ..
출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 그냥 음 내 취향인 문제다. 틀은 잘 짰는데 예외 처리에서 오래 걸렸다. 더보기 먼저, 생각해야 할 부분 1. 같은 티켓이 2장일 수 있다. #Input [["ICN", "SFO"], ["SFO", "ICN"], ["ICN", "SFO"]] #Output ["ICN", "SFO", "ICN", "SFO"]..
출처 : 백준, https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 와 이제 실버 1이다~ 더보기 풀이 #정사각형 테두리 채우기 point = None def fillBorder(left_top, right_bottom, map, target): global point s_i, s_j = left_top e_i, e_j = right_bottom length = (e_j - s_j + 1) * 4 - 4 number = (e_j - s_j + 1)*..
출처 : 백준, https://www.acmicpc.net/problem/4396 4396번: 지뢰 찾기 지뢰찾기는 n × n 격자 위에서 이루어진다. m개의 지뢰가 각각 서로 다른 격자 위에 숨겨져 있다. 플레이어는 격자판의 어느 지점을 건드리기를 계속한다. 지뢰가 있는 지점을 건드리면 플레이어 www.acmicpc.net 더보기 풀이 def makeNumber(current, map, output): i, j = current di = [0, 1, -1, 0, -1, -1, 1, 1] dj = [1, 0, 0, -1, -1, 1, -1, 1] mine = 0 if map[i][j] == '*': return True for index in range(8): ni = i + di[index] nj = ..
출처 : 백준, https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 와 이 코드 156ms로 백준에서 Python3 풀이 중에 22등 했다. 대박 조건 설명이 너무 어려워서 간단하게만 설명하면, 학생들은 자신이 좋아하는 친구 4명을 선정하여 제출하였습니다. 우리는 다음과 같은 규칙에 따라 학생들의 자리를 선정해야합니다. 1. 각 자리를 기준으로 상하좌우에 내가 좋아하는 친구가 많이 앉아있는 자리를 우선합니다. 2. 좋아하는 친구가 많이 ..
