출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 먼저, 생각해야 할 부분 1. 합을 줄이려면 각 요소를 최소화 해야한다. 풀이 def solution(A,B): answer = 0 A.sort() B.sort(reverse=True) for i in range(len(A)): answer += A[i] * B[i] return answer 각 요소의 크기를 줄이려면 가장 큰 값과 가장 작은 값을 곱하면 된다. 이를..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12923 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 먼저, 생각해야 할 부분 1. 조건이 상당히 많다. 패턴을 찾는 것도 중요하지만 조건을 따로 기록하며 빼먹지 않도록 주의하자. 2. 효율성 테스트가 실패가 뜬다면, 1번을 마음에 새기자............ 풀이 #자기자신을 제외한 가장 큰 약수 def maxYaksuExceptMe(number): if number == 1: return 0 for i in rang..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12902 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 먼저, 생각해야 할 부분 1. 익숙하다. 2 x n 타일링에서 많이 보았다. DP에서 한 단계로 묶일 수 있는 것이 무엇이 있는가 생각해보자. 3 x n이므로 입력으로 홀수는 들어올 수 없다. 즉, n은 짝수만 가능하다. 2. 점화식을 제대로 구하는 것이 중요하다. 예제를 살펴보면서 채울 수 있는 형태가 어떤 것이 있는지 고려해보자. 풀이 def solution(n)..
출처 : LeetCode, https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 회사 분의 추천으로 리트코드를 시작해보았다. 문제가 영어라 내 해석에 확신을 가질 수 없다......... 이제 더 이상 백준에서 건드려볼 수 있는 문제들이 남지 않아서 스피드런은 힘들 것 같다........ 파이썬은 새로운 알고리즘을 뚫는 용도로 사용하고, JS로 언어를 바꿀 준비를 해야할 듯 하다. ..
출처 : 백준, https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 더보기 먼저, 생각해야 할 부분 1. 로봇이 움직일 수 있는 방향은 오른쪽과 아래 밖에 없다. 어떤 칸에 도착했을 때 얻을 수 있는 자원의 최대 양은 어떤 것을 비교해야할까? 풀이 n, m = map(int, input().split()) blocks = [[0 for _ in range(m+1)]] for _ in range(n): blocks.append(..
출처 : 백준, https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 더보기 먼저, 생각해야 할 부분 - 풀이 def calcWay(start, end, map): s_x, s_y = start e_x, e_y = end #시작점으로부터 가로 세로 통일 for i in range(s_x, e_x + 1): map[i][s_y] = map[s_x][s_y] for j in range(s_y, e_y + 1): ma..
출처 : 백준, 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:..
