항해9932 [JavaScript] 프로그래머스: n + 1 카드 게임 난이도 : Level 3알고리즘 유형 : 그리드문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258707 문제 풀이각 라운드 마다 2장의 카드가 주어지고 1 장당 1 코인으로 카드를 살 수 있다. 사지 않은 카드는 버려진다.이후 라운드를 끝내기 위해 카드의 합이 n + 1이 되는 2장의 카드를 낸다. 그럼 정석적으로 생각한 다면 시나리오는 다음과 같다.카드 뭉치에서 앞으로 나오는 카드의 종류를 보고 내가 사야하는 카드인지 판단.해당 카드를 살 수 있는지 판단.손에서 카드의 합이 n + 1이 되는 카드 제출. 하지만 카드 뭉치에서 내가 사야하는 카드인지 판단하는 로직이 까다로울 것 같았다.그래서 일단 각 라운드마다 주어지는 카드 2장.. 2024. 12. 2. [JavaScript] 백준 1958번: LCS 3 난이도 : 골드 4알고리즘 유형 : 다이나믹 프로그래밍문제 링크 : https://www.acmicpc.net/problem/1958 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 주어진 여러 개의 수열 모두의 부분 수열이 되는 수열들 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP 와 CAPCAK의 LCS는 ACAK이다. 문제 풀이주어진 문제처럼 3개의 문자열이 아닌 2개의 문자열에서 LCS를 구하는 방법을 생각하고, 이후 3개의 문자열에서 찾을 수 있도록 방법을 넓히자! 시간 내로 문제를 풀기 위해 다이나믹 프로그래밍으로 공통 부분 수열의 길이를 배열에 저장할 것이다. 점화식if (a_str[i] === b_str[j]) dp[i+1][j+1] =.. 2024. 12. 1. [JavaScript] 백준 17609번: 회문 (투 포인터) 난이도 : 골드 5알고리즘 유형 : 투 포인터문제 링크 : https://www.acmicpc.net/problem/17609 문제 풀이회문 판별투 포인터 알고리즘을 이용하여, 양가에서 중간으로 범위를 좁혀오면서 회문인지 판단한다.index 0부터 시작하여 증가하는 포인터인 left와, 문자열의 마지막 index 부터 시작하여 감소하는 포인터인 right를 정의한다.left 일 동안 left++, right-- 하면서 word[left] === word[right] 를 만족하면 회문이다.중간에 left 인덱스의 문자와 right 인덱스의 문자가 다르면 회문이 아니다.유사 회문 판별중간에 left 인덱스 문자와 right 인덱스 문자가 다르면 유사회문인지 일반 문자열인지 판단해야한다.일단 유사회문인지 .. 2024. 11. 30. [JavaScript] 프로그래머스: 표현 가능한 이진트리 난이도 : Level 3알고리즘 유형 : 트리 탐색문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150367 문제 풀이주어진 숫자를 이진수로 변환포화이진트리의 노드 갯수는 무조건 2 ^ n - 1이므로 포화이진트리가 될 떄까지 앞에 9을 붙임이진트리 처럼 루트 노드 부터 left → right 로 순회한다.순회하다가 나오는 값이 1이면 자식 노드들을 순회하고, 순회하다가 나오는 값이 0이면 자식 노드들의 값이 0인지 확인한다. 0이 아니라면 구성 불가능한 트리임으로 0을 반환한다. function solution(numbers) { let answer = []; numbers.forEach(number => { .. 2024. 11. 29. [JavaScript] 프로그래머스: 택배 배달과 수거하기 난이도 : Level 2알고리즘 유형 : 그리드문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150369 문제 풀이메인 생각 : 가장 먼 거리에 있는 집 부터 최대 용량으로 배달 및 수거하기.택배를 배달 및 수거하면서 최소로 이동하려면 한 번 나갈 때 최대한의 택배를 배달/수거해야 한다.또한 제일 멀리있는 집 부터 택배를 배달/수거해야지 최소 거리로 이동할 수 있다. 더보기택배를 전달하기 위해서 앞에서부터 순차적으로 전달 또는 뒤에서 부터 순차적으로 전달하는 방법을 떠올릴 수 있다. 이때 최대한의 택배를 앞에서부터 전달하는 경우 뒤에서부터 전달할 때보다 더 많이 이동할 수 있다. 예를 들어 cap이 4이고 delivery가 [0, .. 2024. 11. 26. [JavaScript] 백준 11657번: 타임머신 (벨만 포드) 난이도 : 골드 4알고리즘 유형 : 벨만 포드문제 링크 : https://www.acmicpc.net/problem/11657 문제 풀이한 정점에서 다른 모든 정점으로의 최단 거리 테이블 구성음의 순환이 있는지 확인위 두가지의 경우를 확인할 수 있는 알고리즘은 벨만 포드와 SPFA가 있다. 이번 문제에서는 벨만 포드로 풀어볼 것이다. 벨만 포드는 정점의 갯수 - 1 만큼 간선들을 반복 연산하여 최단 거리 테이블을 갱신한다.음의 순환이 없고, 단순히 최단 거리 테이블을 구하는 것이라면 위의 계산으로 최단 거리 테이블을 얻을 수 있다.하지만 음의 순환이 있는지 확인하기 위해서는 한 번 더 간선들을 연산하였을 때, 테이블이 갱신되는 지 확인해야한다. 모든 간선들을 V - 1 만큼 반복하여 최단 거리 테이블 .. 2024. 11. 26. 이전 1 2 3 4 ··· 6 다음