potato's devlog

문제 링크 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 내가 푼 풀이 우선 이전 2xn타일링 문제에서는 규칙을 발견하고 그냥 피보나치 방식으로 풀었다. 이 문제는 그 문제의 연장선이기는 하지만, 피보나치 수열 규칙으로는 풀 수가 없었다. 정확하게 왜 그런 방식으로 문제를 풀었는지 이해하는 것이 중요했다.. 우선 풀이에 앞서 경우의 수를 구하는 방식과 원리에 대해서 이해해보자. [1, 2, 3, 4] 의 배열이 있을 때 , 이 숫자들로 만들 수 있는 순열을 작성해보면 다음..

문제 링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 내가 푼 풀이 처음에도 이게 왜 동적계획법인지 몰랐다. 인터넷을 대충 참고해보니, 타일링 갯수가 늘어나는 규칙이 피보나치와 닮아있다는 사실을 발견하면 쉽게 풀릴 수 있다고 했다. 정말, 그림을 그리며 풀이과정을 생각해보니 일정한 규칙대로, 피보나치 수열의 형태로 숫자가 증가함을 알 수 있었다. 그래서 bottom up 방식으로 for 문을 이용하여 풀었다. dp 문제에서 기억할 것은, dp 배열은 항상, 경..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 내가 푼 풀이 bottom up 방식으로 문제 풀이 dp 배열의 인덱스가 숫자를 뜻하고, value가 그 인덱스까지 도달할때 최소 경우의 수이다. 즉, dp 배열에는 그 숫자까지 도달할때의 경우의 수를 메모이제이션 해두는 것이다. 1번규칙 (3으로 나누어 떨어진다) dp[n] = d[n/3] +1 바로 직전 (3의배수니까 n/3) 경우의 수 에서 1을 더해주는 것 2번규칙 (2로 나누어 떨어진다) dp[n] = dp[n/2] +1 3번규칙 (1을 뺀다) dp[n] = dp[n-1]+1 1을 빼는 건,..

Dynamic Programming (동적 계획법) 동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. - Wikipedia ▷ 코딩테스트에서의 DP 코딩테스트의 단골 문제로 출제되고 있기에 필수적으로 알아야하는 개념 중 하나이다. 간혹 제약사항에 주어지는 숫자의 범위가 크고, 경우의 수가 엄청 많은 문제들이 대부분 DP(동적계획법) 을 활용하여 풀어야 하는 문제이다. Dynamic Programming (동적 계획법) 방법 모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는..

문제 링크 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 해결 아이디어 함수 isPrimeNumber 현재 입력받은 수까지 무슨 소수가 존재하는지 배열로 정리 예를들어 9가 입력되면, [2, 3, 5, 7] 이 반환된다. main 입력받은 num 까지 무슨 소수가 존재하는지 isPrimeNums 배열 생성 2부터 num/2 까지 반복 왜 num/2 냐? 10을 예로 들면, (3, 7), (5, 5) (7, 3) 이렇게 골드바흐 파티션이 3..

문제 링크 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 내가 푼 풀이 2부터 차근차근 나눠주면서 print 해줌 범위는 숫자 num까지로 설정했음 마지막에 1이 아닌경우 소수로 마무리 지어졌다는 뜻이므로, 마지막 소수도 출력해줌. 굳이 정렬은 필요없음. 2부터 시작해서 가장 작은 소수부터 출력되게 됨 import Foundation var num = Int(readLine()!)! let n = Int(sqrt(Double(num))) for i in stride(from: 2, to: num, by: 1) { while num % i == 0 { num /=..

문제 링크 https://www.acmicpc.net/problem/2089 내가 푼 풀이 - 맞았습니다! 복잡하게 생각하지 않고 if문으로 상황을 나누어서 문제를 풀었다. 조금 더 효율적인 코딩 방법을 찾아봐야겠다. var num = Int(readLine()!)! var ans = "" while true { if num == -1 { ans += "11" break } else if num == 0 { ans += "0" break } else if num == 1{ ans += "1" break } if num 0 ..

문제링크 https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 내가 푼 풀이 - 시간초과 (어디서 시간복잡도를 줄여야할까요?) 해결 완료 input으로 숫자 하나하나씩 끊어서 배열로 저장 숫자 하나씩 2진수로 구하고, reverse 해줄거임 314 이면, 11 / 001 / 100 이 되어야함 1을 2진수로 구하면 1임. --> 이놈을 세자리수로 모조리 채워주기 위해 앞에 0 두개를 넣어주어야함. 이런 과정이 필요하므로, if 문을 사용해서 0을 넣어줌 대신, 3처럼 맨앞에있는 숫자인 경우에는 011 로 바꿔줄 필요가 없으므로, 그냥 11로 두기 위해서 i..

문제 링크 https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 내가 푼 풀이 생각보다 오래걸렸다. 고민스러운 부분이 상당히 많은 문제인 것같다. 나중에 이런 진법문제는 그냥 풀 수 있도록 2진법과 10진법 계산법 말고 3진법, 8진법, 16진법 등 기본적으로 진법변환을 어떤 규칙으로 해주어야 하는지 알아두는것이 중요할 것 같다. (8진법 어케 구하는지 몰라서 찾아본 1인.... 하... 무식그자체다 ㅠㅠ ) 진법 구하는 방법 기본적으로 알아야할듯 3자리씩 끊어서 2^0, 2^1, 2^2 연산으로 2진법 구하는 방식으로구해준 뒤, 각자리에 넣어주는거임 ..

문제 링크 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 최대공약수구할 때 사용 (유클리드 호제법) input에 담겨있는 수들의 GCD를 구해주고 더해서 출력해줌 let n = Int(readLine()!)! func gcd(_ m: Int, _ n: Int) -> Int { if n == 0 { return m } else { return gcd(n, m%n) ..