맛대의 블로그

https://www.acmicpc.net/problem/2174로직구현문제땅의 현 상태를 저장하기 위해 2중 배열 생성(arr)각 로봇의 현재 좌표를 저장하기 위한 Object(robotPosition) => 배열로 만들었으면 좀 더 좋았을 듯각 로봇의 현재 방향을 저장하기 위한 배열(robotDirection)로봇의 명령왼쪽, 혹은 오른쪽으로 4번 돌게 되면 같은 방향을 보게 됨 => 명령 수를 4로 나머지 연산한 값만큼 수행회전을 구현하기 쉽게 하기 위해 { 'N':0, 'E':1,'S':2,'W':3 } 으로 저장 => 오른쪽 회전 시 1씩 증가, 왼쪽 회전시 1씩 감소// inputconst fs = require('fs');const URI = process.platform === 'linux..

https://www.acmicpc.net/problem/7682로직구현문제한줄을 완성 시키는 경우 게임이 즉시 종료됨입력값에 '.'이 있는데 완성 된 줄이 없는 경우 => 불가능선공은 X로 X가 완성 시킬 경우 O보다 한번 더 두게 되어있음 => X개수와 O개수가 같을 수 없음후공은 O로 O가 완성 시킬 경우 X와 동일한 개수를 두었음 => X와 O의 개수가 같아야만 함X와 O가 동시에 완성 시키는 경우는 존재하지 않음두줄을 한번에 완성 시킬 경우, 두 줄이 겹치는 부분이 존재해야 함 => bingo에 저장된 좌표의 수로 확인세 줄이 완성되는 경우의 수는 불가 (X와 O의 개수가 맞지 않음)개인적인 후기오랜만에 javascript를 이용하여 알고리즘 문제를 풀다보니 Array 다루는 데 애를 먹어서 오..

https://www.acmicpc.net/problem/2302 로직 좌석은 좌,우로 이동이 가능 (n)개의 좌석의 경우의 수 = (n-1)개 경우의 수에서 자기 자리에 앉는 경우 + (n-2)개 경우의 수에서 왼쪽과 바꿔 앉은 경우 dp[n] = dp[n-1] + dp[n-2] n = 1인 경우 : 1 n = 2인 경우 : 12 / 21 n = 3인 경우 : 2인 경우(12 / 21)에서 3을 자기 자리에 앉는 경우 + 1인 경우(1)에서 왼쪽과 바꿔 앉는 경우 즉 (123 / 213) + (132)로 3가지 vip 좌석은 고정 N이 5, vip 좌석이 3이라고 가정 3을 기준으로 왼쪽 두칸(1,2)과 오른쪽 두칸(4,5)가 자유롭게 좌석이 변경 가능 왼쪽 두칸을 배열하는 경우의 수(dp[2])와 오..

https://www.acmicpc.net/problem/23083 로직 입력값이 많아서 nodeJS의 readline 활용 구멍 체크 구멍은 최대 10000개 => 탐색에 시간이 많이 소모됨 지도(꿀벌집)에 표현시 코드가 복잡해짐 (arr[r][c] = ~~~구조에서 각각 빈 곳인지 확인하는 로직이 들어가야함) Set 자료구조 활용 r,c 번째에 구멍이 있을 경우를 체크 => r * C +c 로 변경하여 해당 좌표에 구멍이 있는지 확인 Python과 달리 [1,1]배열을 Set에 추가하여도, 새로운 객체인 [1,1]가 있는지 확인시 false 반환 계산 1,1부터 N,R 까지 탐색 비틀어 있지 않은 경우 2,2를 가능 방법은 1,2 // 2,1 에서 가는 방법의 수의 합 이 문제의 경우 벌집이 비틀어져..

https://www.acmicpc.net/problem/2195 로직 그리디 알고리즘 만들고자 하는 문자열(P)에서 맨앞문자를 시작지점으로 고정해두고, 끝점을 한칸씩 이동하며 잘라진 문자를 한번에 복사 가능 한지 확인 한번에 복사 불가능 할 경우, 복사 횟수를 늘리고 문자열의 시작지점을 해당 지점으로 변경 후 다시 확인 const fs = require("fs"); const URI = process.platform === 'linux'?'dev/stdin':'./2195.txt'; const inputs = fs.readFileSync(URI).toString().trim().split('\n'); const S = inputs.shift(); const P = inputs.shift(); let a..

로직 입력값의 숫자들을 우선순위 큐에 넣으면서 갱신하는 형태 N번째 큰 수를 찾으면 되므로 큐의 크기를 N으로 유지하며 작은 값을을 쳐내는 구조 고민한 것 처음에는수의 배열이 자기보다 위에 있는 숫자보다는 크다는 점을 이용하려고 했습니다. 맨 마지막 줄의 숫자들을 우선순위 큐에 넣고 그 중 가장 큰 수를 빼면서 그 위에 있는 숫자를 넣는다 이를 N번 반복한 결과값이 N번째 큰 수 그래서 2중 배열 형태로 숫자를 저장하려고 했습니다. 하지만 메모리 제한이 12mb로 최대 N 값인 1500*1500 크기로 array를 저장시 메모리 부족으로 실패하게 됩니다. 그렇기에 위 방법으로는 해결할 수가 없어서 입력값이 들어오는대로 처리하고 메모리를 없애야 문제가 해결이 됩니다. readLine ? python으로 알..

https://www.acmicpc.net/problem/11663 로직 이진탐색 활용 현재 값이 배열에서 어느 위치(현재 값보다 작은 값이 몇개 있는지)를 확인 이 떄 끝나는 점은 해당 값이 포함이 되야함 => 현재값+1의 값을 탐색 a부터 b까지의 선에 점이 몇개 있는지 탐색 가정 a보다 작은 값의 개수 확인 => A b보다 작거나 같은 값의 개수 확인(b+1 확인) => B b보다 작거나 같으면서 a보다는 큰 값의 수 = B-A const fs = require('fs'); const URI = process.platform === 'linux'? 'dev/stdin':'./11663.txt'; const inputs = fs.readFile..

로직 그리디 문제 사람의 위치와 햄버거 위치를 각각 배열로 만들어 관리 두 배열이 정렬된 상태에서 맨 앞사람부터 현재 자신이 먹을 수 있는 햄버거가 있는지 탐색, 있다면 그 중 제일 앞index의 햄버거를 섭취 뒷사람은 맨 앞 햄버거와 거리가 멀어 섭취가 불가능 할 수 있기에, 뒷사람이 먹기 가장 어려운 햄버거를 섭취 만약 먹을 수 있는 햄버거가 없다면, 그 사람은 포기(아무도 안먹은 햄버거의 위치가 사람 위치보다 K보다 멀 떄) const fs = require('fs'); const URI = process.platform ==='linux'? 'dev/stdin':'./19941.txt'; const inputs = fs.readFileSyn..

https://www.acmicpc.net/problem/17390 로직 누적합 이용 S부터 E 구간까지의 합 = 0부터 E 구간까지의 합 - 0부터 S 구간 까지의 합 새로운 배열을 만들고, 해당 배열엔 값을 누적하여 값을 기록 배열이 [1,2,3] 이라고 했을때, 누적합 배열은 [0,1,3,6] 으로 만듬 이 때 누적합 배열의 0번 인덱스를 0으로 해둔 것은 1번(0번 인덱스)부터 시작할 때 사용하는 값 배운것 기존에는 input을 받을 때 inputs = fs.readFileSync ~~ 형태로 받은 뒤 배분하는 형태로 사용 이를 [firstLine,secondLine,...datas] 형태로 값을 받으면 간편하게 배분 가능하다 Javascript의 Array의 sort는 기본적으로 str기준으로 ..

https://www.acmicpc.net/problem/1890 로직 게임판과 같은 사이즈의 N*N배열(check)을 만들고, 그 지점에서 몇개의 경로로 목표에 도착 가능한지를 기록 dfs을 이용하여 탐색 이동은 오른쪽과 아래로만 가능 오른쪽으로 이동한 결과 과거에 그 지점을 탐색한 적이 있으면 check에 값이 기록되어 있음 해당 지점에서 목표에 도착을 못할 경우 -1 값 기록 해당 지점에서 목표에 도착 가능할 경우 경우의 수기록 주의사항 및 알게된 점 이 문제에서 경로의 최대 개수는 2^63-1 이하 JavaScript의 number type의 최대 값은 2^53-1 따라서 BigInt를 이용하여 계산해야 함 BigInt는 number와의 연산이 불가 [BigInt(1)+1이 불가] N*N배열을 만..