분류 전체보기
-
BOJ) 동전 2알고리즘/백준 2020. 7. 27. 23:57
동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 풀이 방금 전 포스팅한 LIC 문제보다 푸는데 조금 더 많은 시간이 걸렸다. 먼저, 동전 1과 다르게 k원을 만드는 최소 값을 구해야 한다는 조건이 까다롭게 느껴졌다. 또한, 만들 수 없는 경우 -1을 리턴해야한다는 부분을 간과했다. 마지막으로 고민한 부분은 점화식을 어떻게 세우는가였다. 우선 coin의 값이 뒤죽박죽일 수 있기 때문에, Arrays.sort를 통해 오름차순 정렬을 해주었다. 이후, 답이 될 dp[k]는..
-
BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)알고리즘/백준 2020. 7. 27. 23:51
가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다. 다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다. 그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다. 먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다. 이후, 탐색을 통해 자신보다 큰..
-
JS 표준 입력 방법 (node.js readline), 비동기(Async & Await)패턴Java Script/기본 개념 정리 2020. 7. 27. 22:49
표준 입력 readline 모듈 이용 const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); // 한 번 입력 rl.question(">>문자를 입력해주세요 : ", (line) => { rl.close(); console.log(line); // 입력 값 찍어보기 }); // 여러번 입력 rl.on("line", (line) => { if(line === "quit") rl.close(); console.log(line); }); rl.on('close', () =>{ process.exit(); }); question 한 번 입력, 파..
-
Git fork, push 취소, commit 취소Git 2020. 7. 27. 22:45
git fork gir fork는 레파지토리 오른쪽 상단에 보면, fork 있어서 누르면됨 push 취소 // 가장 최근의 commit을 취소 (기본 옵션: --mixed) $ git reset HEAD^; // 브랜치와 HEAD가 가리켰었던 커밋 목록 확인 $ git reflog 또는 $ git log -g; // 원하는 시점으로 되돌리기 $ git reset HEAD@{number} 또는 $ git reset \[commit id\]; // 되돌려진 상태에서 다시 커밋 $ git commit -m "commit message"; // 다시 푸쉬 $ git push origin +\[branch name\] commit 취소 // commit 목록 확인 $ git log // [방법 1] commit을..
-
자바스크립트 구성요소 ~ 함수는 값을 반환한다Java Script/MDN 정리 2020. 7. 26. 19:06
반환 값이란 let myText = 'The weather is cold' let newString = myText.replace('cold', 'warm') console.log(newString) // Should print "The weather is warm" // the replace() string function takes a string, // replaces one substring with another, and returns // a new string with the replacement made replace() 메소드의 작동 원리 'cold' substring을 찾는다. 해당 substring을 'warm'으..
-
BOJ) 가장 큰 증가 부분 수열알고리즘/백준 2020. 7. 26. 17:33
가장 큰 증가 부분 수열 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이 다이나믹 프로그래밍 문제는 너무 어렵다.. ㅠㅠ 다른 문제 유형보다 생각을 조금 많이 요한다. 많은 실패를 겪고 답을 찾았다. 먼저, 각 index에서 취할 수 있는 가장 큰 증가 부분 수열의 합을 저장할 dp를 선언해준다. 이후 for문을 통해 index를 탐색하면서( i ) dp[i] 에 최대값을 저장한다. 최대값을 저장하는 과정은 0부터 해당 index 전 까지 for..
-
BOJ) 달팽이는 올라가고 싶다알고리즘/백준 2020. 7. 26. 17:27
달팽이는 올라가고 싶다 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 풀이 달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다. A는 달팽이가 낮에 올라갈 수 있는 높이이고, B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다. 정상에 올라간 후에는 미끄러지지 않는다. 위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다. 잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 ..
-
BOJ) 합분해알고리즘/백준 2020. 7. 26. 15:48
합분해 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0~ N까지의 정수 K 개를 선택하여 N을 만드는 경우의 수를 구하는 문제다. 덧셈의 순서가 다르면 다른 경우로 체크한다. (1 + 2 와 2 + 1 은 다른 경우) 각각의 수는 여러번 이용 가능하며, 1,000,000,000으로 나눈 나머지를 출력해야한다. 우선 k개를 이용했을 때, 특정 숫자 n을 구할 수 있는 경우의 수를 담기 위해 2차원 배열의 dp를 선언했다. int[][] dp = new int[k][n]; 우선 k = 1 일 때, (0 ~ N까지 하나만 이용했을 때) 숫자를 만들 수 있는 경우를 1로 저장해줬다. (0이든, 1이든 ... N이든 자기 자신을 딱 하..