분류 전체보기
-
[KOITP] N-Queen자료구조 및 알고리즘/문제풀이 2016. 12. 19. 09:29
출처 : http://koitp.org/problem/NQUEEN/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초256 MB949483 (51%)378문제N-Queen문제는 유명한 문제이다. 이는 N × N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오.입력첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 12)출력첫 번째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.힌트예제 입력4 예제 출력2 BackTracking 에 대해서는 그다지 어렵다는 인상이 아니어서 대충 가능할 거라고 여겼는데, 다시 한 번 봐야 할 것 같습니다. 생각보다 한참 고민하면서 풀었습니다. ..
-
[KOITP] 동전 교환자료구조 및 알고리즘/문제풀이 2016. 12. 12. 00:58
출처 : http://www.koitp.org/problem/COIN/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB1497333 (22%)253문제우리나라 동전 단위는 1원, 5원, 10원, 50원, 100원, 500원의 6단계로 이루어진다. 잔돈 256원을 내주려면, 100원 2개, 50원 1개, 5원 1개, 1원 1개로 해서 모두 5개의 동전이 필요하다.만약 동전 단위가 1원, 4원, 6원의 3단계로 이루어진 나라에서 잔돈 8원을 내주려면 6원 1개, 1원 2개도 가능하고, 4원 2개로도 가능하다. 앞의 경우에는 동전이 3개, 뒤의 경우에는 동전이 2개 필요하다.동전의 개수를 최소로 하면서 동전을 내주는 것이 목적이라면 뒤의 방법을 택해야한다. 동전들의 단위가..
-
[KOITP]Matrix Chain Multiplication자료구조 및 알고리즘/문제풀이 2016. 12. 12. 00:56
출처 : http://www.koitp.org/problem/MATRIX_CHAIN_MULTIPLICATION/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB278106 (38%)95 문제M×NM×N 크기의 행렬 AA와 N×KN×K 크기의 행렬 BB의 행렬 곱셈 ABAB를 생각해보자. 두 행렬의 곱셈 과정의 연산 횟수는 MNKMNK 이다. 행렬 곱셈에는 교환 법칙 AB=BAAB=BA는 성립하지 않지만, 결합 법칙 (AB)C=A(BC)(AB)C=A(BC)는 성립한다. 결합 법칙에 의해 어떤 순서로 곱셈을 하는지에 따라 전체 연산 횟수가 차이난다. 예를 들어, 세 행렬 A1,A2,A3A1,A2,A3가 있다고 하자. A1A1은 10×10010×100 크기, A2A2는 1..
-
[KOITP] LCS자료구조 및 알고리즘/문제풀이 2016. 12. 12. 00:55
출처 : http://www.koitp.org/problem/LCS/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB424126 (30%)111 문제LCS(최장 공통 부분수열, Longest Common Subsequence)란, 두 수열이 있을 때 두 수열의 공통 부분수열 중 가장 긴 공통 부분수열의 길이를 의미한다. 예를 들어, 수열이 1,4,2,51,4,2,5와 1,2,3,4,51,2,3,4,5의 LCS는 1,2,51,2,5이다. LCS 문제는 수열이 아닌 문자열에서 주로 다루기도하는데 이 때 문자열의 각 문자가 수열의 수에 해당한다고 보면 된다. 따라서 두 문자열 "ABCBDAB", "BDCABA"의 LCS는 "BCBA"가 된다. 두 문자열이 주어졌을 때, 두..
-
[KOITP] 막대기 자르기자료구조 및 알고리즘/문제풀이 2016. 12. 12. 00:54
출처 : http://www.koitp.org/problem/ROD_CUTTING/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB297150 (51%)132 문제길이가 NN인 막대기가 있다. 막대기를 길이가 자연수가 되도록 여러 조각으로 자를 수 있다. 각 길이에 대해 값어치가 있을 때, 값어치 합이 최대가 되도록 막대기를 자르자. 예를 들어, 길이가 4인 막대기가 있고 각 길이 별 값어치가 아래와 같다고 하자.| length | 1 | 2 | 3 | 4 | |----------|---|---|---|---| | cost | 1 | 5 | 8 | 9 | 이 때, 길이 2인 막대기가 두 개가 되도록 전체 막대기를 자를 경우 전체 값어치가 10 되어 최대가 된다.입력첫..
-
[KOITP] Assembly Line Scheduling자료구조 및 알고리즘/문제풀이 2016. 12. 12. 00:43
출처 : http://www.koitp.org/problem/ASSEMBLY_LINE_SCHEDULING/read/ 시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.0 초512 MB441133 (30%)120문제명우네 공장에는 두 개의 생산라인이 있고, 각 라인에는 nn개의 공정이 순서대로 있다. 하나의 제품이 완성이 되려면 두 생산라인 중 한 생산라인을 정해, 그 생산라인에 미완성 제품이 들어가고 그 생산라인의 nn개의 공정을 순서대로 지나, 생산라인에서 생산을 마무리하여 완성된다. 중간에 생산라인을 바꿀 수도 있다.첫 번째 생산라인의 ii번째 공정에서 소요되는 시간은 S1,iS1,i이고, 두 번째 생산라인의 ii번째 공정에서 소요되는 시간은 S2,iS2,i이다. 그리고 첫 번째 생산라인에 ..
-
이하이 - 한숨snack/음악 2016. 12. 12. 00:18
숨을 크게 쉬어봐요당신의 가슴 양쪽이 저리게조금은 아파올 때까지숨을 더 뱉어봐요당신의 안에 남은 게 없다고느껴질 때까지 숨이 벅차올라도 괜찮아요아무도 그댈 탓하진 않아가끔은 실수해도 돼누구든 그랬으니까괜찮다는 말말뿐인 위로지만 누군가의 한숨그 무거운 숨을 내가 어떻게헤아릴 수가 있을까요당신의 한숨그 깊일 이해할 순 없겠지만괜찮아요내가 안아줄게요 숨이 벅차올라도 괜찮아요아무도 그댈 탓하진 않아가끔은 실수해도 돼누구든 그랬으니까괜찮다는 말말뿐인 위로지만 누군가의 한숨그 무거운 숨을내가 어떻게헤아릴 수가 있을까요당신의 한숨그 깊일 이해할 순 없겠지만괜찮아요내가 안아줄게요 남들 눈엔 힘 빠지는한숨으로 보일진 몰라도나는 알고 있죠작은 한숨 내뱉기도 어려운하루를 보냈단 걸이제 다른 생각은 마요깊이 숨을 쉬어봐요그대..
-
민경훈, 김희철 - 나비잠snack/음악 2016. 12. 8. 20:58
어느덧 흘러간 시간을 수놓을 수 있는 밤 짧지 않던 세월 서로가 가까워진 지금을 웃으며 기억하고 싶어 끝이 온다 말을 해도언젠가 헤어진다 해도 내일 당장 사라져도 잊어버리게 하지 않도록 기억하도록오래 지나도 잊을 수 없게 기억하도록 오늘을 되돌아보며 감은 두 눈에 머금고꿈 속까지 미뤄 잠이 들 테죠 마지막 바람이 불며 끝나는 날을 알려도함께 했던 추억 사진의 빛이 바래진대도 웃으며 기억하고 싶어 끝이 온다 말을 해도언젠가 헤어진다 해도 내일 당장 사라져도 잊어버리게 하지 않도록 기억하도록오래 지나도 잊을 수 없게 기억하도록 오늘을 되돌아보며 감은 두 눈에 머금고 꿈 속에 담아내려 잠이 들 테죠 봄의 꽃, 여름의 나비, 가을의 낙엽그 겨울의 달빛 펼쳐진다면우리의 추억 또한 영원히 곁에 떠오르니까 시들 수 ..