💾 Algorithm/문제 풀이41 [JavaScript] 백준 2206번: 벽 부수고 이동하기 문제 정보난이도 : 골드 3알고리즘 유형 : BFS문제 링크 : https://www.acmicpc.net/problem/2206 문제 풀이(1, 1)에서 (N, M)까지 이동하는 최단 경로를 찾는 문제다. 맵에는 벽이 있지만, 단 한 번만 벽을 부술 수 있는 능력이 있다. 모든 인접한 칸으로의 이동 비용은 동일하기 때문에 BFS를 활용하여 최단 경로를 구할 수 있다. 이 문제에는 벽을 한 번 부술 수 있다는 조건이 있다.따라서 동일한 위치에 도달하더라도 아래의 2가지 상태가 나올 수 있다.벽을 한 번도 부수지 않은 상태로 도달한 경우이미 벽을 한 번 부수고 도달한 경우앞으로의 경로 선택에 영향을 미치기 때문에, 이 두 상태는 서로 다른 상태로 관리해야 한다. 일반적인 BFS에서는 방문 여부를 bool.. 2025. 5. 12. [JavaScript] 백준 30804번: 과일 탕후루 문제 정보난이도 : 실버 2알고리즘 유형 : 투 포인터, 슬라이딩 윈도우문제 링크 : https://www.acmicpc.net/problem/30804 문제 풀이최대 2가지의 과일만이 존재할 수 있다.정답이 되는 위치를 미리 알 수 없으므로, 처음부터 시작하여 2가지의 과일만 사용한 가장 긴 꼬치를 찾아야 한다.기본 아이디어:새로운 탕후루 꼬치(newTanghuru) 배열을 만들어 현재까지 유효한 과일 조합을 관리한다.과일 종류를 추적하기 위해 Set 자료구조(currentTypes)를 사용한다.배열을 순회하면서 조건에 맞게 과일을 추가하거나 꼬치를 조정한다. 알고리즘 동작 과정 예시:예를 들어, 과일 종류가 [1, 2, 3, 2, 1, 3]이라고 가정해보자.처음 1을 만남: newTanghuru =.. 2025. 5. 11. [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. 이전 1 2 3 4 ··· 7 다음
