PS/백준

문제 https://www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net How to Solve ? function solution(duck) { let cnt = 0; let idx = 0; let first = true; const word = ["q", "u", "a", "c", "k"]; const visited = Array(duck.length).fill(false); if (duck.length % 5 !== 0) return -1; for (let i = 0; i < du..

2021. 7. 9.

PS/백준

문제 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 전체 코드 function solution() { // 같으면 0 출력. if (A === B) return 0; // 정렬 했을 때, 다른 값이라면 순서로 해결 불가능. const sortedA = A.split("").sort().join(""); const sortedB = B.split("").sort().join(""); if (sortedA !== sortedB) return -1; // 뒤집어서 같으면 2로 나눈 후, 반올림 co..

2021. 7. 7.

PS/백준

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제를 이해했는가? 제곱수로만 N을 만들 때, 최소한의 개수를 출력하라. 어떻게 풀 수 있지? 이 문제는 전형적인 DP이다. 왜 그럴까? 같이 생각해보자. 1. 완전 탐색 당연히 브루트포스로 풀면서, 접근을 해볼 수도 있지만 문제 속에서는 '시간을 0.5초' 로 제한을 하였다. 보통 1초에 연산을 1억번 한다고 가정 하기 때문에 가볍게 생각해보면 5천만번의..

2021. 7. 6.

PS/백준

문제 https://www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 문제에 대한 이해 밤마다 특정 길이만큼 빠르게 자라나는 n개의 나무 중 1개를 벨 때 n일동안 얻을 수 있는 최대 길이를 출력하라. 이해를 디테일하게 처음에는 하루하루 업데이트를 하면서, 그 날짜에 얻을 수 있는 최대의 값을 얻는 문제라고 생각을 하였다. 하지만 주어진 답과 맞지 않아서 고민을 해보니 "최대의 나무"를 얻기 위해서는 성장 속도가 긴 나무는 늦게 베어주는게 더 효과적 이라는 사..

2021. 6. 30.

PS/백준

문제 https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 문제를 이해했는지? 각 상자의 넓이와 높이, 그리고 보내고자 하는 사탕의 개수가 주어 졌을 때 포장 가능한 최소한의 박스 수를 출력하시오. 풀이방법 - 그리디 function solution() { let count = 0; let sum_weight = 0; const new_box = []; // 가로 * 세로로 박스가 담을 수 있는 사탕의 수를 계산 box_sizes.forEach((each..

2021. 6. 29.

PS/백준

문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제를 이해했는가? 팰린드롬이면 0, 1개만 바꾸면 팰린드롬이 되면 1, 아예 안되면 2를 출력하라. 구현 1) 팰린드롬이 되려면 "짝수 + 뒤집어도 같아야함" 2) 유사 팰린드롬을 찾으려면 " 홀수 + 하나만 지우면 됨" 3) 아니라면 짝수와 홀 수 일 때 1,2의 조건에 해당 안되면 function solution(word) { word = word.split(""); let reversed = word.slice()..

2021. 6. 29.

PS/백준

문제 https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 문제를 제대로 이해 했는지? 한 사람이 테이블에 있는 햄버거를 집을 수 있는 범위를 줬을 때, 얼마나 많은 인원이 햄버거를 먹을 수 있는지 출력하시오. 풀이 방법에 대한 고찰 1) 최대한 많은 사람이 햄버거를 먹으려면? 자신의 앞의 햄버거 중에서 가장 먼 것을 고를 때, 다른 사람이 햄버거를 잡을 수 있는 확률이 증가 2) 범위만큼 순회를 ? 범위만큼 루프를 돌아도 될까? 라는 의문을 가졌..

2021. 6. 29.

PS/백준

문제 https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 문제를 이해했는가? 대진표의 결과를 주었을 때, 다음과 같은 결과를 만들 수 있는지 여부를 판단하는 프로그램을 만들어라. 문제 이해를 디테일하게 예시에 주어진 아래의 결과를 바탕으로 이야기 해보자. 5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 위의 결과지는 "참"인 1을 출력 할 수 있는데, 그 이유는 아래의 두 가지이다. 1) 패배의 수와, 승리의 수가 같다 2) 무승부 수..

2021. 6. 28.