[JS][백준]16236_아기 상어

문제 번호 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 풀이 아기 상어는 현재 자신의 몸 크기에 따라서 먹을 수 있는 물고기가 있고 먹을 수 없는 물고기가 있다. 따라서 먹이를 먹을때 마다 아기 상어의 몸의 크기를 확인하여서 먹을 수 있는 물고기들의 위치, 거리를 계산해야한다. 이를 위해서 BFS 를 사용하였다. 왜냐하면 BFS는 간선의 가중치가 1로 같을때 최단 경로를 찾아주기 때문이다. BFS로 맵을 탐험하면서 아기 상어..

→2021.09.17

Algorithm/BaeKJoon

[JS][백준]5582_공통 부분 문자열

문제 번호 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 알고리즘 분류 DP 문제 풀이 2차원 배열을 사용해서 공통 부분 문자열을 찾는 문제이다. 공통 부분 문자열은 연속된 문자열이다. 해당 문제는 아래의 블로그에 나온 설명이 도움이 많이 되었다. 그래서 따로 설명을 쓰는것보다 링크를 추가하는것이 더 좋다고 생각된다. [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(L..

→2021.09.17

Algorithm/BaeKJoon

[JS][백준]17179_케이크 자르기

문제 번호 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 알고리즘 분류 이분 탐색, 그리디 문제 풀이 이분 탐색을 사용해서 '가장 작은 케이크의 길이'를 '최대'로 만드는 문제이다. 케이크를 자르면 가장 작은애가 나오게 될텐데 걔의 길이를 가능한 길게 하라는 말이다. 여기서 이분 탐색은 '가장 작은 케이크의 길이'를 찾는데 사용된다. 왜 이분 탐색을 사용하는지 생각해보면 '가장 작은 케이크의 길이'가 '최대'일때를 구하려면 케이크를 자를 때 마다 가능한 중앙에서 ..

→2021.09.17

Algorithm/BaeKJoon

[JS][백준]17070_파이프 옮기기 1

문제 번호 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 알고리즘 분류 DP, 그래프이론 문제 풀이 문제에서 파이프는 2칸을 차지한다고 하여서 처음에는 head 와 tail 로 나누어서 좌표를 기록하려 했다. 하지만 한쪽의 좌표만 기록해도 문제를 해결할 수 있다. 그래서 가장 처음상태의 (1,2) 에 있는 좌표만 사용하면서 문제를 해결한다. (1,1)에 있는 파이프는 신경쓰지 않아도 된다. 어차피 (1,1)은 고정이고 그 다음부터는 그래프 탐색과 다름없기 때문이다. 그래프이론, DP,..

→2021.09.15

Algorithm/BaeKJoon

[JS][백준]17406_배열 돌리기4

문제 번호 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 알고리즘 분류 구현, 브루트포스 문제 풀이 브루트포스를 이용하여 문제에서 주어진 연산들을 수행할 모든 순서를 정한다. 나는 이 순서들을 operationOrder 라는 배열에 넣어주기로 하였다. // 회전 연산의 경우의 수. let operationOrder = []; let end = K; function BTS() { if (end === 0) { //console.log(operationOrder); return ro..

→2021.09.14

Algorithm/BaeKJoon

[JS][백준]12871_무한 문자열

문제 번호 12871번: 무한 문자열 첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 알고리즘 분류 수학, 구현, 문자열 문제 풀이 검색해보면 LCM을 이용하는 방법들이 주로 나온다. 그래서 나는 다른분께 질문해서 들은 내용으로 문제를 풀어보려고한다. 최대공배수를 구한다음 주어진 문자열들을 최대공배수 만큼 자른다. 그 후 잘린 문자열들을 비교해서 모두 같은내용이라면 '1' 이다. const fs = require('fs'); const input = fs.readFileSync('무한 문자열/input.txt').toString().trim().split('\n'); let s = in..

→2021.09.14

Algorithm/BaeKJoon

[JS][백준]3190_뱀

문제 번호 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 알고리즘 분류 구현, 자료구조, 시뮬레이션, 덱, 큐 문제 풀이 구현문제다. 그래서 알고리즘은 어렵지 않다. 다 풀고나서 백준에 있는 알고리즘 분류를 보니 덱과 큐 가 있었다. 아마도 뱀의 이동경로를 기록하기 위해서 사용하는 용도같다. 나는 문제풀때는 이 생각을 못해서 배열에 이동경로를 넣고 shift 하면서 뱀의 꼬리를 움직였다.(선입 선출 구조이므로 queue를 생각하고 풀었으면 생각의 정리가 더 편했을것 같다.) JS 스텍, 큐 큐, 스택, 트리 | J..

→2021.09.10

Algorithm/BaeKJoon

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

문제 번호 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 알고리즘 분류 구현, 시뮬레이션 문제 풀이 보통 시뮬레이션/구현 문제들은 문제에서 주어진 순서대로 작성하면 쉽게 문제가 해결되었다. 그런데 이번 문제는 2단계의 b를 가장 마지막에 확인하였다. 문제에서 주어진 순서대로 작성하였더니 2단계의 b번을 확인하는 과정에서 아래의 c와 d를 확인하지않고 a와 b만 무한 반복하는 현상이 벌어졌기 때문이다. 물론 a b c d 순서대로 확인하는 방법도 있을거라 생각하지만 나는 a c d b 의 순서로 확인하였다. ..

→2021.09.09

티스토리툴바