Algorithm/BaeKJoon

    [JS][백준]17845_수강 과목
    Algorithm/BaeKJoon

    [JS][백준]17845_수강 과목

    문제 번호 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 문제 풀이 처음엔 그리디를 활용한 문제인 줄 알았다. 그래서 단위 시간당 중요도를 계산해서 그 결과값이 높은 순서로 수강 과목을 선정하려 했으나 오답인걸 알았다. 문제를 다시 살펴보니 DP를 사용해야 하는 문제라는 생각이 들었고 중요도와 공부시간이라는 2개의 입력이 있는 걸 보고 Knapsack을 사용할 수 있을지 생각해보았다. Knapscak 알고리..

    [JS][백준]14503_로봇 청소기
    Algorithm/BaeKJoon

    [JS][백준]14503_로봇 청소기

    문제 번호 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 풀이 BFS를 활용한 구현 문제이다. 별다른 어려운 내용 없이 흔히 사용하는 BFS를 문제에서 주어진 조건에 맞게 돌리면 된다. 단, 문제에서 '북:0 동:1 남:2 서:3'라고 주어진다. 처음에 이 부분을 놓쳐서 청소기의 회전 방향을 반대로 하는 바람에 시간이 오래 걸렸었다. dx, dy 란 배열을 만들어서 동서남북 각 방향으로 회전할 때 좌표의 변화를 나타낼 수 있도록 한다. 이때 문제의 입력과 배열들의 인덱스를..

    [JS][백준]15566_개구리 1
    Algorithm/BaeKJoon

    [JS][백준]15566_개구리 1

    문제 번호 15566번: 개구리 1 연못 안에 개구리들이 있을 수 있는 연꽃 N개와, 연꽃 사이를 연결하는 다리 역할의 통나무 M개가 있다. 같은 연꽃 쌍을 연결하는 통나무의 개수는 1개 이하이다. 여기에 N마리의 개구리가 각각 www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 백트래킹 문제 풀이 입력이 길어서 당황했지만 문제를 읽어보면 백트래킹을 이용해서 브루트포스를 진행하면 풀 수 있다는 것을 알 수 있다. 처음에는 개구리들을 모두 배치하고 나서 DFS로 정답여부를 판별하려 했으나 그것보다는 개구리를 한마리 한마리 배치하면서 정답에 부합하는지 확인하는것이 더 적절하다고 판단했다. 우선 연꽃이 비어있는지, 이미 개구리가 앉있는지 확인할 배열과 자리를 잡지 못한 개구리가 있는지 확인할 배열을..

    [JS][백준]6137_문자열 생성
    Algorithm/BaeKJoon

    [JS][백준]6137_문자열 생성

    문제 번호 6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N = tail) break; } // 사전순으로 빠른 문자부터 push 한다. if (s[head] CCC // CCCC 같은 문자열이 주어지는 경우를 생각해보자. 마지막으로 주어진 문자열 S에서 1개를 제외하고 모든 문자를 T에 추가했을때의 경우를 생각해준다. if (head === tail) { // 마지막 1개의 문자가 남았을때. T.push(s[head]); break; } 문제에서 80개의 ..

    [JS][백준]16139_인간-컴퓨터 상호작용
    Algorithm/BaeKJoon

    [JS][백준]16139_인간-컴퓨터 상호작용

    문제 번호 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 알고리즘 분류 누적 합 문제 풀이 일반적인 누적합 문제이다. 각 알파벳별로 누적합을 구해서 문제를 해결하면된다. 2차원 배열을 만들어서 각 알파벳별로 누적합을 구한다음 문제에서 주어지는 구간에 사용된 알파벳의 수를 구하였다. 전체코드 const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n'); function ma..

    [JS][백준]15990_1, 2, 3 더하기 5
    Algorithm/BaeKJoon

    [JS][백준]15990_1, 2, 3 더하기 5

    문제 번호 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 처음에는 점화식을 세워서 풀이를 진행하려고 했다. 하지만 이렇다 할 규칙을 찾아내지 못하여서 2차원 배열을 사용한 DP알고리즘을 사용하면 더 쉽고 직관적인 풀이가 가능하다는 것을 알았다. 처음에 생각해본것은 DP알고리즘을 사용할 것이기 때문에 N을 만들기위해서 N-1, N-2, N-3 들을 어떻게 활용할 것인가 였다. N-1 에서 N에 영향을 줄 수 있는 방법은 1을 더하는 것뿐이다. 그리고 하나 더 고려해야 할 점은 같은 수는 연속해서 올 수 없다는 점이다...

    [JS][백준]2729_이진수 덧셈.
    Algorithm/BaeKJoon

    [JS][백준]2729_이진수 덧셈.

    문제 번호 2729번: 이진수 덧셈 이진수 덧셈은 매우 간단하고, 십진수 덧셈과 비슷하게 하면 된다. 십진수 덧셈을 할 때는, 오른쪽부터 왼쪽으로 차례대로 숫자 하나씩 더하면 된다. 이진수 덧셈도 이와 비슷하게 하면 된다. 십 www.acmicpc.net 알고리즘 분류 수학 구현 사칙연산 문제 풀이 이진수의 덧셈을 직접구현한다. 입력받은 두개의 수 중에서 더 긴쪽의 길이만큼 더 짧은쪽에 0을 채워서 넣는다. let max = s1.length > s2.length ? s1.length : s2.length; s1 = s1.padStart(max+1, '0'); s2 = s2.padStart(max+1, '0'); 이후 보통 숫자를 계산하는 방법대로 계산하면된다. function main() { let a..

    [JS][백준]22857_가장 긴 짝수 연속한 부분 수열 (small).
    Algorithm/BaeKJoon

    [JS][백준]22857_가장 긴 짝수 연속한 부분 수열 (small).

    문제 번호 22857번: 가장 긴 짝수 연속한 부분 수열 (small) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 브루트포스 알고리즘 두 포인터 문제 풀이 투 포인터를 사용해서 모든 경우의 수를 찾아보는 문제이다. 투 포인터를 사용하는데 편리하게 하기 위해서 nums라는 배열에 0이라는 의미 없는 숫자를 추가해주었다. 투 포인터의 start와 end는 이 '0'을 가리키면서 시작한다. const nums = [0]; 이후 배열의 숫자가 짝수인경우 'sum'이라는 변수를 1개씩 늘려가면서 연속된 짝수가 몇 개인지 파악한다. if (nums[end] % 2 === 0..

티스토리툴바