명왕성의 공전기록

https://school.programmers.co.kr/learn/courses/30/lessons/68645 이 문제는 2차원의 배열에 반시계 방향으로 숫자를 채운 뒤, 배열 순서대로 숫자를 반환하는 문제다. 처음 문제를 보았을 때는 풀지 못했던 문제인데, 백준에서 다양한 알고리즘 풀이 방식에 대해 공부하게 되면서 풀 수 있게 되었다. 생각한 로직은 다음과 같다. 먼저 다음과 같은 2차원 배열을 생성한다. 이때, 해당 배열은 삼각형 형태를 띄어야하므로, 인덱스에 따라 커지게 만들었다. 이후 하, 우, 좌상으로 이동하며 빈칸을 채우는 로직을 구현한다. 이때 해당 칸이 채워져 있을 경우나, 범위를 벗어나는 경우 이를 처리할 수 있는 함수도 함께 구현한다. (BFS나 DFS에서 사용하는 방식을 응용하였다..

해당 문제 풀이는 구글에 자바스크립트 풀이 방법이 존재하지 않길래 포스팅하게 되었다. https://www.acmicpc.net/problem/14940 풀이 방식은 다음과 같다. 1. 먼저 "2"로 표현된 목표 지점을 찾는다. 그리고 이를 찾는 과정에서 "원래갈 수 있는 땅인 부분 중 도달할 수 없는 위치"는 "-1"로 표현되어야 하므로, 전체적인 배열 matrix에서 "1"로 표현되어 있는 값을 미리 모두 -1로 수정한다. (findStarting 함수) 2. BFS 함수를 구현한다. 로직은 [이동거리, 위치] 를 요소로 갖는 queue를 사용하여 구현했고, visited 배열을 통해 이미 방문한 곳은 다시 방문하지 않도록 했다. 이때, 상하좌우로 이동하였을 때 이동이 가능한지를 확인하여("0"이 아..

https://www.acmicpc.net/problem/12865 문제는 최대로 담을 수 있는 무게와 담으려는 물품이 주어질 때, 배낭에 넣을 수 있는 물건들의 가치합의 최대값 요하는 문제다. // limit = 5 // data = [ [ '6', '13' ], [ '4', '8' ], [ '3', '6' ], [ '5', '12' ] ] const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split("\n").map((x)=> x.split(" ")) const [_, limit] = input.shift().map(el=>..

문제는 다음과 같다. 0,1 로 이루어진 이차원 배열에서, 1로 이루어진 가장 정사각형을 만들었을 때 가장 큰 넓이를 구하는 문제다. 그리고 이 문제에 접근하기 위해 동적 계획법(Dynamic Proramming)이라는 개념에 대해 알게 되었는데, 이에 대해 먼저 나눠보기로 한다. 동적 계획법(Dynamic Proramming)이란? 입력 크기가 작은 부분 문제들을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 전체 문제를 해결하는 알고리즘 설계기법이다. 따라서 동적 계획법을 사용하기 위해선 큰 문제를 작은 문제로 나눌 수 있어야 하며 작은 문제들의 해결 방법은 모두 동일해야 하고 작은 문제들의 해결 결과는 한 번만 계산하고 저장해 놓을 수 있어야 한다. 피보나치 수열은 ..

미로 찾기 관련 DFS 문제를 풀다가, 이미 방문했던 곳을 다시 방문하지 않기 위해 방문 내역을 저장하기 위한 배열을 구현하던 도중 new Array와 Array.from의 차이점에 대해 알게 되어 이에 대해 예를 들어 포스팅해본다. 1차원 배열의 경우 먼저 일반적인 new Array / Array.from으로 배열 길이가 n이며, 0으로 채운 배열을 만든다고 한다면 다음과 같다. const n = 2 let arr1 = new Array(n).fill(0) // [0,0] let arr2 = Array.from({length : n}, ()=> 0) // [0,0] new Array 객체를 사용한 방식의 경우, 숫자를 인자로 받아 해당 숫자만큼의 길이를 가진 배열을 생성한다. (fill은 배열을 채우는..

DFS, BFS는 모두 그래프를 탐색하는 알고리즘이다. 먼저 node란? 그래프 이론에서 주로 사용되는 용어로, 트리나 그래프 구조의 개별적인 요소를 의미한다. 위 그림에서도 보여지는 것과 같이, DFS와 BFS의 차이점은 어떤 방식으로 다음 노드를 탐색하느냐에 따라 나뉜다. (색상으로 구분했다.) DFS (깊이 우선 탐색) DFS의 경우는 그 말마따나, 인접한 노드를 '깊이'있게 모두 탐색한 뒤에 다음 노드로 넘어가는 방식이다. 느리기는 하지만 간단하며, 모든 노드를 방문하고자 하는 경우에는 위 방법을 사용하며 스택 또는 재귀함수로 구현된다. (DFS는 미로에서 100% 탈출하는 방법이라고 말하는 수법(손을 활용한 방식)과 비슷한 방법이라고도 볼 수 있는데, 궁극적으로 두 방법은 모든 경로를 파악하며 ..

coalece / date_format / order by, having 오늘은 프로그래머스 MySQL SQL문 문제를 풀며 알게 된 내용들에 대해 다룬다. 먼저, 문제는 다음과 같다. coalece 다음 문제에서는 이름이 Null 값인 동물의 이름을 "No name"으로 치환하여 보여주는 것을 원한다. SELECT ANIMAL_TYPE, coalesce(NAME,'No name') as NAME, SEX_UPON_INTAKE FROM ANIMAL_INS ORDER BY ANIMAL_ID 이때, coalesce 라는 함수는 처음 사용해보았는데, coalesce는 null이 아닌 첫번째 유효한 표현식을 반환하는 함수이며 이 함수 덕분에 name컬럼 내에 존재하는 Null 값을 "No name"으로 치환하여..

기념하기 희희