파이문

2293. 동전 1(https://www.acmicpc.net/problem/2293) 동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS) 구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다. 예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다. 유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ..

11053. 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053) 유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS) 일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다. 동영상 설명이 잘 되어 있어서 링..

2579. 계단 오르기(https://www.acmicpc.net/problem/2579) 문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.) 계단이 4개 있을 때로 문제를 늘리면 1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4]) 왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보..

수열에서 연속된 구간의 최대 합 구하기Largest Sum Contiguous Subarray / Maximum subarray problem 유명한 문제로, 주어진 수열에서 최대 합을 구하는 것이 요점이다. 쉽게 생각하자면 O(n^2)으로 구하면 되지만 (Brute Force), 대부분의 문제 풀이 사이트에서는 O(n)으로 풀기를 권고하고 있다. 제일 무난 한것이 Dynamic Programming으로 푸는 것인데, Kadane’s Algorithm이라고 한다. 현재 까지의 구간의 최대 합과, 해당 숫자와 Max 값을 비교하고 이 값을 다시 전체 합과 Max 값을 비교하는 것이다.class Solution: def maxSubArray(self, nums): """ :type nums: List[int..

파이썬 딕셔너리의 키(Python dictionary key) 디시인사이드 프로그래밍 갤러리에 들어갔다가 재미난 글을 발견했다. "파이썬에서 다음 중 딕셔너리의 키로 쓸 수 있는 것들은?" 이라는 제목의 글이었는데, 다 돌려보았는데.. 일단 나는 답을 틀렸다 ㅠㅠa = lambda : 0 b = [0] c = (0,) d = {0} e = frozenset(d) f = {0: 0} class Foo: pass g = Foo() a, c, e, g이다. 나머지 것들은 딕셔너리의 키로 사용하지 못한다. 파이썬의 딕셔너리는 기본적으로 해시 키를 사용한다. 좋은 article을 몇 개 찾았는데 이 글 이 되게 좋은 것 같다. 그리고 frozenset 이라는걸 들어는 봤는데, 언제 쓰는지, 정확히 set 과 무슨..

518. Coin Change 2(https://leetcode.com/problems/coin-change-2/#/description) amount 를 coins의 값들로 만들 수 있는 모든 경우의 수를 리턴하는 문제다. 원래는 coin들로 recursive 하게 빼주다가 0이 되면 리턴하게 하는 식으로 하려고 했는데, 빼주었던 coin들을 어떻게 가지고 있어야 할지 구현하는게 어려워서 포기했다. 결국 DP로 풀었는데, 2차원 배열로 어떻게 하려다가 잘 안되서 그냥 인터넷에서 보고 구현했다. dp의 index값은 amount 값이 되고, 그렇기에 0원을 만들 수 있는 경우의 수는 1가지 (아무것도 없는 경우) 있기 때문에 dp[0] = 1 을 해준 상태에서 시작한다. amount 5, coins = ..

1149. RGB 거리(https://www.acmicpc.net/problem/1149) dp[i][j]라는 배열을 만들어서, i는 i번째 집이고 j는 색을 의미하게 하였다. 그 값으로는 i번째 집이 j의 색을 가질 때, 가질 수 있는 최소 값을 넣었다. 정리하자면 i번째 집을 j색으로 칠할 때 + (i-1번째 집이 j색이 아닌 다른색으로 칠했던 경우의 최소 값) 인 것이다. public void problem1149(int houseCount, ArrayList n) { int[][] dp = new int[houseCount][3]; dp[0][0] = n.get(0); dp[0][1] = n.get(1); dp[0][2] = n.get(2); for (int i=1; i

1463. 1로 만들기(https://www.acmicpc.net/problem/1463) 동전 경우의 수 구하는 문제랑 비슷하다. 다만 앞에서 하는게 아니라 뒤에서 풀어야 풀린다. (다른 방법은 잘 모르겠음) 예를 들어서 8이 주어지면 8에서 만들 수 있는 수는 8-1, 8/2 두 가지이다. 이 때 나오는 수인 7, 4를 인덱스로 가지는 dp 에 1을 넣어준다. 이것이 맨 처음에 1을 넣어주는 부분이다. (초기화를 n-1하는 이유는 어떤 수 n에서 1을 만드는 가장 최댓값이 n-1이기 때문이다.) 그리고 그 다음 7부터 거꾸로 dp를 만들어 주면 된다. (인덱스) i에서 i/2, i/3, i-1에 i를 만들수 있는 값 + 1과 해당 값의 최솟값만 갱신해 주고, 목표가 1을 만드는 것이기 때문에 dp의 ..

1003. 피보나치 함수(https://www.acmicpc.net/problem/1003) 숫자를 입력받아, (피보나치 계산으로) 1과 0을 얼마나 호출하는지를 출력하는 문제이다. 케이스 범위에 따라, 이전 계산 값을 그대로 사용할 수 있게 보완하면 더 좋을듯 public void problem1003(int n) { if (n == 0) { System.out.println("1 0"); } else if (n == 1) { System.out.println("0 1"); } else if (n == 2) { System.out.println("1 1"); } else { int[][] dp = new int[n + 1][2]; dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1..

[Python] 파이썬 3.5 에서 MySQL 라이브러리 설치하기Error loading MySQLdb module: No module named 'MySQLdb'Django tutorial을 따라하면서 mysql을 연동하려 하는데, mysql-python이 설치되지 않았다. 분명 mysql 설치 시 Connector를 다 설치하였기 때문에 Connector 설치하라는 글은 넘겼고 도저히 원인을 파악하지 못했었는데, 알고보니 단순한 문제였다. Mysql에서 제공하는 Python Connector가 Python 2.7, 3.3, 3.4 버전만 지원하는 것이었다. 나의 경우엔 파이썬 3.5를 사용하였기 때문에 설치가 되지 않았던 것이다. (참고로 mysql-python은 C로 구현되어 있다.) 대안으로는 p..