[문제] https://www.acmicpc.net/problem/1010 [처음 생각] 겹치지 않게 n을 기준으로 했을 때, m중에서 선택하려니 조합이나 순열로 풀리지 않았다. 그래서 반대로 m을 기준으로 했을 때, n중에서 순서없이 선택한다고 생각하니 겹치지 않게 선택할 수 있었다. m개 중에서 n개를 순서없이 선택한다면 선택된 점들은 n개의 점과 차례대로 그냥 이어지면 되기 때문! [풀이] 조합 알고리즘으로 mCn으로 풀었다. 함수 재귀 호출로 점화식을 사용해서 풀었다. [참고] http://bumbums.tistory.com/2 [Code] https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1010/MakeBridge.java
[문제]https://www.acmicpc.net/problem/5582 [처음 생각]전에 LCS 문제 푼 것과 비슷하다고 생각이 들었다. LCS 문제는 연속하는 부분 문자열이 아니어도 되었는데 이건 연속한 문자열이므로 더 편하게 풀 수 있겠다는 생각?!첫번째 문자열을 기준으로 두번째 문자열을 하나하나 비교해가며 최대한 긴 공통 부분 문자열을 찾으려고 했는데 이렇게 하면 시간 복잡도가 클 것 같다는 생각이 들었다. 블로그를 참고해서 힌트를 얻었다. [풀이]각 문자열의 길이만큼의 2차원 배열을 생성한다. 이 배열을 이용해서 만약 해당하는 위치의 문자가 서로 같다면, 즉 a.charAt(i) == b.charAt(j)라면 dp[i][j]에 이전의 dp[i-1][j-1]값에 1을 더한 값을 할당한다. 대신 배..
[문제]https://www.acmicpc.net/problem/2293 [처음 생각]쿠팡 알고리즘 시험에서 2번 문제로 나왔던 문제와 똑같다. 그때 검색으로 풀어서 답은 맞았지만 다시 주면 못풀것 같아서 다시 풀어보려 한다...생각해봐도 그냥 for문으로 돌리는것말고는 dp로 잘 모르겠음... 점화식이 안세워짐 ㅜㅜ [풀이]dp[i] 를 i원을 만들기 위한 경우의 수 배열로 생성한다.예제를 사용해서 설명한다면...dp[10]은 dp[9]에 1원을 더한 것과 dp[8]에 2원을 더한 것과 dp[5]에 5원을 더한 것의 합과 같다.dp[10] = dp[9] + dp[8] + dp[5]이렇게 dp[9]와 dp[8], dp[5]를 마찬가지 방법으로 분해해서 생각한다.계속 쪼갰을 때 점화식 dp[k] = dp[..
[문제]https://www.acmicpc.net/problem/1509 [처음 생각]dp 배열을 어떤 의미로 정의할지부터 생각이 들었다. -> 어려워서 전체 코드 다 보고 따라씀... [풀이]팰린드롬(Palindrome) : 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 1. 팰린드롬의 모든 경우를 만든다.2. 만들어진 2차원 배열을 검사하며 최소 개수를 구한다. (이 최소 개수를 구하는 과정이 이해가 잘 안감) [참고]http://wootool.tistory.com/109 http://joonas-yoon.blogspot.kr/2016/04/1509.html [Code]https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1509/Di..
[문제]https://www.acmicpc.net/problem/1562 [처음 생각]0에서 9까지의 모든 수를 사용해서 각 자릿수의 차이가 1이 나는 계단수를 N 길이 만큼 만드는데 이게 몇 개가있는지 구한다(단 0으로 시작할 수 없다.) 예제에 있는 N이 10일때는 생각했을 때 '9876543210' 1가지밖에 없어서 이걸 10^9으로 나눈 1이 답인 것 같다. [풀이]모르겠어서 풀이를 찾아봤는데 비트마스크를 사용한 코드밖에 없었다. 그래서 일단 비트마스크 공부를...밑의 첫번째 블로그에서 10자리 자릿수의 계단수의 끝자리가 0에서부터 9가 될 수 있고 이 때 계단수에 존재하는 숫자들의 OR값이 bit가 된다는(!!!) 이 말이 무슨 말인지 이해가 안간다... [참고]http://katekimm.ti..
[문제]https://www.acmicpc.net/problem/2133 [처음 생각]dp로 푼다는걸 알고 나서 점화식을 세워보려고 했다. 하나씩 따져보니까 n이 홀수일때는 아예 타일을 채우기 불가능했다. [풀이]dp는 점화식을 세우고 그 점화식을 위해서 초기값을 만들어두어야 한다는걸 깨달았다. 마치 피보나치 수열 점화식처럼...? [참고]http://mrl.kr/jungol2133/ http://browoo.tistory.com/entry/%EB%AC%B8%EC%A0%9C2133-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0 [Code]https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_2133/Tile.java
[문제]https://www.acmicpc.net/problem/11726 [처음 생각]3 x n 타일링 문제를 먼저 풀고 접해서 그런지 홀짝의 차이구나라고만 생각이 들었다. 근데 점화식을 세워보니 3xn 타일링 문제보다 훨씬 쉬웠다. 전처럼 dp[0]을 1로 놓고 1부터 차례대로 그려나가보니 그냥 피보나치 수열이었다. [풀이]피보나치 수열처럼 풀었다. 재귀로 메소드를 호출해서 dp배열에 값을 저장해나가며 큰 문제를 해결하는 방식으로 풀었다. 처음에는 시간초과가 났는데 그 이유는 메소드에if(dp[nn] > 0) return dp[nn]; 안해줬기 때문이다.이걸 써줘야 하는 이유는 만약 미리 계산된 dp[nn] 배열값이 있다면 그냥 바로 return 해주면 되는데 이게 없다면 다시 배열값을 계속 계산해줘..
[문제]https://www.acmicpc.net/problem/2579 [처음 생각]처음 문제를 읽고서는 골프존 1차 면접에서 봤던 1번 개구리가 징검다리를 건너는 문제가 생각났다. 그 문제도 징검다리에 숫자가 적혀있었고 대신 이 문제처럼 제약조건이 없었던 것 같다. 개구리가 도착지에 도달할때까지의 max 값을 구하는 문제였다. -> dp 문제였다는걸 깨닫지 못하고 풀어서 틀렸던 것 같음(면접관이 답 틀렸다고 했고 나도 다른 테스트 케이스 작성해서 넣었을 때 답이 나오지 않았음) [풀이] [참고] [Code]https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_2579/Stairs.java
- Total
- Today
- Yesterday
- BOJ
- 12100
- 13460
- 이진 탐색
- 1037
- 이진 검색
- 7569
- 째로탈출2
- acmicpc
- parametric search
- 자료구조
- 알파벳 찾기
- ACM Craft
- mybatis
- combination
- 단어 공부
- 파라메트릭
- 1157
- acmpicpc
- Java
- 약수
- 1085
- 알고리즘
- 7576
- lottie
- 2048 game
- 조합 알고리즘
- spring
- 위상정렬
- 10809
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |