티스토리

개발새발 로그

검색하기

블로그 홈

개발새발 로그

ydoag2003.tistory.com/m

개발하면서 배워온 것들 들어가라잇!

구독자: 3

방명록 방문하기

주요 글 목록

[JS] 백준 11792 : 하노이 탑 이동 순서 - 재귀 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로www.acmicpc.net 풀이방법1. 세 개의 장대 -> 시작 장대, 나머지 장대, 목적지 장대라는 기준을 둔다.2. 두 번의 수행과정을 거쳐야함 - 1. 첫번째로 맨 밑의 원반을 제외한 원반들은 모두 나머지 장대에 옮겨져야한다. -그래야 맨 밑의 원반이 목적지 장대로 갈 수 있다. -원반의 개수가 몇개던 간에, 시작 장대(start)에서 목표기둥(final)으로 모든 원반을 옮기기 위해서맨 밑의 .. 공감수 0 댓글수 0 2023. 9. 20.
[JS] 백준 2164 : 카드2 - 큐, 스택, 링크드리스트(push,pop의 비효율) https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net push나 pop을 사용하면 시간초과가 뜨는 문제다 배열의 연산시간상 맨 앞 요소의 삭제 & 추가하는 연산이 index 수정시간하는 시간이나 다름없기 때문에 연결리스트를 만들어서 사용해야 한다. JS는 연결리스트가 없어서 직접 만들어주면 된다. ☝링크드리스트 링크드리스트는 노드로 이루어져 있고 val, ref,add 저장 - find 를 위해서는 시간복잡도 O(n) - random access를 .. 공감수 0 댓글수 0 2023. 9. 12.
[JS] 백준 1149 - RGB거리 - DP https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 📋풀이방법 1. 주어진 빨강, 초록, 파랑의 값을 아래의 점화식으로 처리한다. dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0] dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1] dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + rgb[n][2] - dp배열안에 각각의 색.. 공감수 0 댓글수 0 2023. 9. 7.
[JS] 백준 9059 : 1, 2, 3 더하기 - DP https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 📋풀이방법 1. 1과 2와 3으로 만드는 것이므로 일단 1, 2, 3의 숫자를 만들 수 있는 경우의 수를 수동으로 세본다. 2. 그럼 아래와 같이 나오게 된다. 3. 이후의 숫자를 다시 수동으로 적으면서 찾아보자 4. 이때 규칙이 생기는데 이전에 구했던 1, 2, 3 의 경우의 수를 이용할 수 있게 된다. 🤟내 제출 var fs = require('fs'); var inputs = fs.readFileSync('/dev/stdin').toString().split('\n').map(v=>Numb.. 공감수 0 댓글수 1 2023. 8. 29.
[JS] 백준 13549번 : 숨바꼭질 3 - 그래프이론, BFS, 너비우선탐색, 덱 자료구조(Double Ended Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 📋풀이방법 1. BFS를 이용한다 2. visited라는 100100정도 크기의 배열을 선언해서 0으로 초기화해준다 -이 배열은 걷기와 순간이동을 할 때 같은 곳을 방문하지 않도록하기 위한 배열임 3. queue에 시작점 N과 시간초 cnt를 넣어주고 visited[N]=1로 방문표시를 해준다. 4. queue에서 하나씩 빼면서 N이 K가 되면 반복을 종료해준.. 공감수 0 댓글수 0 2023. 8. 22.
[JS] 백준 1707 : 이분그래프 - 그래프이론, BFS, 이분그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프(Bipartite Graph)란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는( 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다. 풀이방법 1. 테스트 케이스마다 다른 그래프가 형성된다. 2. u ->.. 공감수 0 댓글수 0 2023. 8. 21.
[JS] 백준 2493번 : 탑 - 자료구조, 스택 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 📋풀이방법 1. 주어진 탑의 높이를 차례로 순회하면서 스택의 top부분과 비교한다. - 1. 스택의 top의 높이가 더 작을 경우 스택의 top부분이 검사하는 높이보다 커질 때까지 pop하면서 반복한다. - 2. 만약 스택의 top높이가 더 클 경우 정답에 해당 높이의 인덱스를 넣고, 검사하는 높이를 스택에 넣어준다. - 3. 만약 스택이 비어있을 경우 검사하는 높이의 값을 스택에 넣어준다. 그.. 공감수 0 댓글수 0 2023. 8. 20.
[JS] 백준 1715번 - 카드 정렬하기 - 우선순위 큐, 최소 힙 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐를 활용해야하는 문제이다. 📋풀이방법 1.최소힙 구조로 우선순위 큐에 주어진 값을 넣고, 루트노드를 두 개 A와 B의 뺀 값 C를 total값에 누적하고, 다시 최소힙에 더한 값 total을 넣으면 원하는 결과가 나온다. 2. 이 때 중요한 것은 우선순위큐 구조를 만드는 것이다. https://chamdom.blog/heap-using-js/ [자료구조] JavaScrip.. 공감수 0 댓글수 0 2023. 8. 18.
[JS] 백준 1520번 : 내리막 길 - 구현, 그래프이론, DFS, 다이나믹프로그래밍(DP) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 📋풀이방법 1. 상하좌우 DFS로 뻗어나간다. 2. 이때 -1로 초기화한 2차원 배열 dp에 목적지까지 도착했는지에 대한 값을 기록한다. 3. 기록하면서 만약 -1이 아니고(방문을 했고) 그 좌표에 값이 있다면 그 값을 return함으로 써 뻗어나가지 않고, 미리 도착을 예상할 수 있다. 🤟내 제출 const fs = require("fs"); const filePath = process.platfor.. 공감수 0 댓글수 0 2023. 8. 16.
[JS] 백준 2110번 : 공유기 설치 - 이분 탐색 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 📋풀이방법 1. 이분탐색 문제이므로 lt와 rt변수를 선언한다. -lt는 1로 초기화한다. -> lt는 각 집마다의 공유기설치 최소거리를 뜻한다. -rt는 주어진 집의 좌표를 오름차순으로 정렬하고 가장 마지막 값으로 초기화한다. -> rt는 각 집마다의 공유기 설치 최대거리를 뜻한다. 2. while반복문으로 lt가 rt보다 작거나 같을 때까지 .. 공감수 0 댓글수 0 2023. 8. 15.
[JS] 백준 1806번 : 부분합 - 누적 합, 투 포인터, 효울성 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 효율성 문제이다. 투포인터를 이용해서 조건에 맞는 수열의 부분합을 찾는 것이다. 📋풀이방법 1. lt와 rt를 사용해야하므로 선언한다. - lt는 0으로 초기화해주고, rt는 for문을 이용해 N까지 증가하면서 순회한다. 2. 0 ~ N까지 순회하면서 result 변수 안에 주어진 수열 arr에서 arr[rt]를 하나씩 누적해본다. 3. 만약 result가 S보다 크거나 같다면 wh.. 공감수 0 댓글수 0 2023. 8. 14.
[JS] 백준 1916번 : 최소비용 구하기 - 그래프이론, 다익스트라 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제이다. 최소힙을 구현했어야했지만 나는 queue을 이용해서 방믄하지않은 노드 중 가장 짧은 거리의 노드를 선택하는 기능을 넣어 구현했다. https://ydoag2003.tistory.com/41 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단경로탐색 알고리즘입니다. 이전에 배운 크루스칼 알고리즘은 최소비용 신장트리이다. .. 공감수 0 댓글수 0 2023. 8. 13.
[JS] 백준 2252번 : 줄세우기 - 그래프이론, 위상정렬, 큐 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이전에 포스팅했던 위상정렬의 문제다 https://ydoag2003.tistory.com/43 위상 정렬 위상정렬 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 사용하는 알고리즘 위상정렬을 통해 여러개의 순서를 조건에 부합하는 일직선의 순서로 만든다. 배고픔 -> ydoag2003.tistory.com 📋풀이방법 1. 연결되어있음.. 공감수 0 댓글수 0 2023. 8. 12.
[JS] 백준 2580번 : 스도쿠 - 백트래킹, DFS https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이방법 1. 스고쿠 맵안에서 0인 곳의 좌표를 모두 찾아 저장한다. 2. DFS를 호출해 카운트 0부터 시작한다 -이는 0인 곳에 숫자를 넣은 후 +1해서 다시 DFS를 재귀호출한다. 3. DFS를 0부터 시작했으므로 0인 곳의 좌표를 저장했던 배열도 인덱스 0부터 시작한다. -0인 곳의 좌표를 순차적으로 뽑아내서 그 안에 숫자를 넣을 것이다. 4. 1 ~ 9까지의 숫자를 모두 넣어보고 가로열,.. 공감수 0 댓글수 0 2023. 8. 11.
[JS] 백준 1717번 - 집합의 표현 - [런타임 에러 (EACCES)], 자료구조, 분리집합, 서로소집합 알고리즘, 그래프이론 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 📋풀이방법 ✅서로소집합 알고리즘을 이용하면 간단하게 풀 수 있다. https://ydoag2003.tistory.com/22 그래프이론(서로소집합) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 합집합(uni ydoag2003.tist.. 공감수 0 댓글수 0 2023. 8. 10.
[JS] 백준 1107번 : 리모컨 - 브루투포스, 완전탐색 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ' 풀이방법 1. 가려고하는 채널을 기준으로 하는 것이 아닌 0번 채널 ~ 9999999번 채널을 모두 탐색하면서 답을 찾는 것이다. 2.먼저 100번에서 +,- 만 눌렀을 때의 누른 횟수와 3. 0~9999999번 채널을 눌러가면서 찾은 최소 누른 횟수를 비교한다 0~9999999번 채널 탐색 1. 예를 들어 순회하면서 현재 50번이라는 채널까지 왔다고 가정하자, 그리고 가려고하.. 공감수 0 댓글수 0 2023. 8. 8.
[JS] 백준 17298번 - 오큰수 - 스택, 자료구조 https://www.acmicpc.net/status?user_id=oridori2705&problem_id=17298&from_mine=1 채점 현황 www.acmicpc.net 📋풀이방법 1. 스택을 이용해서 문제를 풀어야한다. 2. 위 그림대로 주어진 배열의 숫자를 하나씩 검사한다. 🤟내 제출 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let input = fs.readFileSync(filePath).toString().trim(); input = input.replace(/\r/g, "").split("\n"); let [N, temp] = input;.. 공감수 0 댓글수 0 2023. 8. 7.
[JS] 백준 11404번 : 플로이드 - 그래프이론, 플로이드-와샬 https://www.acmicpc.net/status?user_id=oridori2705&problem_id=11404&from_mine=1 채점 현황 www.acmicpc.net 전형적인 플로이드 와샬 알고리즘문제이다. 플로이드 와샬 알고리즘이란? 기존에 다익스트라 알고리즘은 [하나의 정점에서 출발 했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘]입니다. 만약 [모든 정점에서 모든 정점으로의 최단 경로]를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야합니다. https://ydoag2003.tistory.com/42 플로이드 와샬(Floyd warshall)알고리즘 다익스트라 알고리즘은 [하나의 정점에서 출발 했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘]입니다. 만약 [모든.. 공감수 0 댓글수 0 2023. 8. 5.
[JS] 백준 11054번 : 가자 긴 바이토닉 부분 수열 - DP(다이나믹 프로그래밍) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이방법 1. N크기의 배열에 현재 숫자가 뒤에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다 2. N크기의 배열에 현재 숫자가 앞에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다. 3. 두 배열을 구했으면 두 배열의 값들을 인덱스에 대응되는 값끼리 더하고 -1을 한다(자신 숫자가 겹치므로 -1로 제외) 4. 두 배열을 더하는 것은 가운데 숫.. 공감수 0 댓글수 0 2023. 8. 4.
[JS] 백준 2206 : 벽 부수고 이동하기 - 그래프, 이론그래프, 탐색너비 우선 탐색 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 📋풀이과정 1. 이동하는 중에 벽을 부셔야한다 -> 이 조건이 중요하다 2. 이동하는 중에 벽을 부수므로 BFS를 뻗어나갈 때 방문표시할 visited 배열을 3차원배열로 해야한다. -> 이유는 만약 가다가 벽을 부수게 된다면 새로운 방문 배열로 간다 -> 새로운 방문배열은 벽을 부순 후의 방문 배열이다. -> 새로운 방문배열에서 새롭게 다시 BFS를 뻗어나간다 ( 즉 벽.. 공감수 0 댓글수 0 2023. 8. 3.
[JS] 백준 2293번 : 동전 1 - DP (백준 메모리초과) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 📋풀이방법 1. 손으로 풀 수 있을 때까지 문제를 나열해보자 2. 이때 규칙을 찾아야한다. 3. 그림을 봤을 때 1원만 사용했을 때와 1원과 2원을 사용했을 때의 차이가 있다. 4. 차이에서 규칙을 찾아야한다. 5. 이때 중요한 점은 0원일 때의 경우의 수도 넣어야한다. ->0원을 만드는 경우의 수는 0개의 동전을 선택하는 방법이므로 1가지입니다. 🤟내 제출 const fs = require("fs.. 공감수 0 댓글수 0 2023. 8. 2.
[JS] 백준 1978 : 알파벳 - 그래프, 이론그래프, 탐색, 깊이 우선 탐색,백트래킹 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이방법 1.DFS로 상하좌우를 탐색한다. 2. 탐색하면서 지나온 알파벳은 배열에 저장한다. 3. 다음 알파벳을 검사할 때 저장해놓았던 배열을 indexOf로 검사한다 4. -1이 나오면 겹치는 알파벳이 없는 것이므로 진행해준다. 5. 이때 visited라는 2차원 배열로 방문표시를 해줘야 무한재귀가 걸리지않는다. 6. 또한 DFS로 뻗어나갈 때 상하 좌우 모든 경우로 뻗어나가야하므로 저장.. 공감수 0 댓글수 0 2023. 8. 1.
[JS] 백준 1759번 : 암호만들기 - 수학,브루트포스 알고리즘,조합론,백트래킹 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📋풀이방법 1. DFS에서 조합 알고리즘을 이용했다. 2. 트리는 만약 1을 뽑으면 2 3 4를 뽑고 2를 뽑으면 3 4를뽑는형태로 뻗어나간다. 3. L개를 뽑으면 L개의 알파벳을 검사한다 -a, e, i, o ,u가 존재하면 gather라는 변수를 +1한다 -그외에는 consonant라는 변수를 +1한다. 4.gather>=1 && consonant>=2 일 경우에만 result배열에 정답을 넣는다... 공감수 0 댓글수 0 2023. 7. 31.
[JS] 백준 1011번 : Fly me to the Alpha Centauri - 수학 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 수학 알고리즘으로 규칙을 찾아야한다. 💬문제 이해 -아래 그림과 같이 처음과 끝은 1이어야한다. 👁‍🗨규칙 찾기 거리 (y-x) 내용 가동 횟수 1 1 1 2 1 1 2 3 1 1 1 3 4 1 2 1 3 5 1 2 1 1 4 6 1 2 2 1 4 7 1 2 2 1 1 5 8 1 2 2 2 1 5 9 1 2 3 2 1 5 10 1 2 3 2 1 1 6 .. 공감수 0 댓글수 0 2023. 7. 30.
[JS] 백준 9251번 : LCS - DP문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 참고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Comm.. 공감수 0 댓글수 0 2023. 7. 29.
[JS] 백준 7569번 : 토마토(3차원배열) - 구현문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 토마토문제에서 3차원배열을 추가한 것이다. 📋풀이방법 1. 처음에 익은토마토의 위치를 저장한다(well배열) -> 이때 좌표에 0을 추가해서 저장한다(며칠이 걸렸는지를 위해) -처음에 안익은 토마토의 갯수를 세놓는다.(none_well) -visited도 3차원 배열로 선언해줘야한다. 2. [시간초과 주의] well배열의 idx가 well의 length만큼 되었을 때.. 공감수 0 댓글수 0 2023. 7. 28.
[JS] 백준 10025번 : 적록색약 - 구현문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 📋풀이방법 1. 적록색약인 사람과 아닌사람을 구분해서 DFS로 상하좌우를 검사해 그룹을 만든다. 2. DFS할 때 visited를 두개를 생성해서 둘이 따로 구분해준다. 🤟내 제출 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let input = fs.. 공감수 0 댓글수 0 2023. 7. 27.
[JS] 백준 12865 : 평범한 배낭 - DP문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 📋풀이방법 1. 첫번째 물건(무게 : 6, 가치 : 13)을 dp배열에 넣어서 검사한다. 2. 두번째 물건(무게 : 4, 가치: 8)을 넣어 검사해본다. 3. 세번째 물거(무게 : 3, 가치 : 6) 4. 이를 반복해준다. 🤟내 제출 const fs = require("fs"); const filePath = process.plat.. 공감수 0 댓글수 0 2023. 7. 26.
[JS] 백준 1753 : 최단경로 - 다익스트라 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이방법 1. 다익스트라 문제이다. 2. DP문제 같으면서 그래프 문제이다. 3. 시작노드를 기준으로 시작해서 4. 갈 수 있는 인접노드를 탐색 후 5. dist 배열에 그 인접노드 까지의 거리를 넣는다. 6. 이때 만약 현재노드에서 인접노드까지의 거리가 시작노드에서 인접노드의 거리보다 짧다면 7. dist를 짧은 거리로 갱신해준다 8. 갱신 완료 후 9. 현.. 공감수 0 댓글수 0 2023. 7. 25.
[JS] 백준 2447 : 별 찍기 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 📋풀이방법 1. NxN의 좌표를 모두 순회하면서 별을 찍을 자리가 맞는지 확인한다, 2. 확인하는 방법은 아래와 같다. - 1. 만약 x와 y 좌표가 3으로 나눴을 때 나머지가 1이라면 빈칸이다. - if(i % 3 == 1 && j % 3 ==1) ->, (1,1), (1,4) ...이 공백을 출력해야 하는 위치인 것을 알 수 있고, 이 패턴이 반복되기 때문에 i, j.. 공감수 0 댓글수 0 2023. 7. 24.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.