목록전체 글 (305)
백준11722 - 가장 긴 감소하는 부분 수열(DP) node.js
https://www.acmicpc.net/problem/11722 해당 문제는 다이나믹 프로그래밍으로 문제해결이 가능하다. 풀이 과정은 다음과 같다. 먼저 수열의 '길이'를 출력하는 것이므로, DP 테이블의 기본값은 1로 설정한다. (자기 자신만 포함하는 경우) 여기서 두번째 반복문의 범위는 0 arr[i] 조건을 만족하며, 이전 요소를 마지막으로 하는 부분 수열의 길이에서 현재 요소를 추가할 경우의 길이(dp[j] + 1)가, 현재 요소를 마지막으로 하는 부분 수열의 길이(dp[i])보다 큰 경우 dp[i] = dp[j] +1 로 값을 수정해 나아가며 dp 테이블을 완성한다. const fs = require("fs"); const input = fs .readFileSync(process.platf..
백준11055 - 가장 큰 증가하는 부분 수열(DP) Python
https://www.acmicpc.net/problem/11055 해당 문제는 다이나믹 프로그래밍을 활용하여 풀이할 수 있는 문제다. 풀이과정은 다음과 같다. 먼저 가장 큰 부분 수열의 '합'을 구하는 것이므로 DP 테이블의 기본값은 입력값으로 초기화한다. (이는 자기 자신만 포함하는 경우이기도 하다.) 이후 두번째 반복문의 범위는 0 arr[j]) 현재 요소를 마지막으로 한 부분 수열의 합 dp[i]보다 현재 요소 값 + 이전 요소를 마지막으로 한 부분 수열 합(arr[i] + dp[j])의 값이 클 경우 (arr[i] + dp[j] > dp[i]) dp[i] 를 arr[i] + dp[j] 로 수정해준다. import sys data_temp = sys.stdin if sys.platform == '..
class-validator 커스터마이징
먼저 class-validator란, 자바스크립트 또는 타입스크립트에서, 객체의 유효성을 검사하고 검증하는데 도움을 주는 라이브러리다. 이를 사용하면 다양한 유효성 검사 규칙을 정의하고 이를 객체에 적용할 수 있다는 장점이 있다. (예를 들어, 이메일 주소가 올바른 형식인지 확인하거나 비밀번호가 일치하는지 확인하는 등의 검증 규칙을 정의할 수 있다.) 아래는 class-validator를 사용하여, user DTO인 nickname의 길이가 1에서 50 사이인지 검증하는 것을 보여준다. nickname의 길이가 규정한 1보다 작거나, 50보다 클 경우 'Bad Request' 에러를 자동적으로 반환한다. import { Field, InputType } from '@nestjs/graphql'; impo..
백준15989 - 1,2,3 더하기 4 (DP) node.js
https://www.acmicpc.net/problem/15989 해당 문제는 다이나믹 프로그래밍을 활요해야 풀이해야 시간제한 내에 풀 수 있는 문제다. 비슷한 문제를 풀이하고 풀이 과정을 포스팅한 링크를 남긴다. 2023.11.09 - [개발/algorithm] - 프로그래머스 Lv.3 - 거스름돈 (DP) Python 해당 문제의 접근 방법을 소개하기 앞서, 0부터 6까지 [1,2,3]을 활용해서 만들 수 있는 경우를 표로 나타내면 다음과 같다. 0 1 2 3 4 5 6 1을 사용 1 1+1 1+1+1 1+1+1+1 1+1+1+1+1 1+1+1+1+1+1 1,2를 사용 2 2+1 2+1+1 2+2 2+1+1, 2+2+1 2+1+1+1+1 2+2+1+1 2+2+2 1,2,3을 사용 3 3+1 3+1+..
백준13565 - 침투 (DFS) node.js
https://www.acmicpc.net/problem/13565 해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 쉽게 해결할 수 있다. 문제 풀이 과정 이 문제에서 유의할 점이 있다면 백준의 여타 다른 DFS 문제와 달리 모든 좌표에 DFS 알고리즘을 동작시키는 것이 아니다. outer side인 첫 번째 배열에서만 값이 이동가능한 좌표인 경우(0인 경우) DFS 알고리즘을 동작시킨 뒤, 마지막 배열에 방문 기록이 존재하는지 파악 후 답안을 출력했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim..
백준2583 - 영역 구하기 (DFS) node.js
https://www.acmicpc.net/problem/2583 해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 풀이가 쉽다. 문제 풀이 방식은 다음과 같다. 주어진 N,M의 값으로 기본값을 0으로하는 이차원 배열을 선언하고 주어진 직사각형의 좌표를 통해 해당 좌표 내에 포함된 영역을 1로 수정한다. 즉 0은 이동할 수 있는 공간, 1은 이동할 수 없는 공간으로 표현되고 있는 셈이다. 이후 추가적으로 방문 기록을 담기 위한 이차원 배열을 선언한다. DFS 알고리즘 로직을 깊이에 대한 값을 리턴할 수 있게 구현한 뒤에, 결괏값을 구할 수 있다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? ..
백준16946 - 벽 부수고 이동하기 4 (DFS) Python
https://www.acmicpc.net/problem/16946 해당 문제는 DFS 알고리즘을 응용하여 해결할 수 있는 문제다. 풀이 과정은 다음과 같다. 1. DFS 알고리즘을 활용해, 벽이 아닌 방의 크기를 구해나간다. 이때, 방문여부 처리를 하여 이전에 방문했던 곳을 다시 방문치 않게 하며, 방 번호 변수를 선언하여 각 공간마다 구분할 수 있게 방 번호를 매기고, DFS 알고리즘 종료 시 리턴되는 방 번호(깊이)와 방 크기를 함께 저장한다. def solution (data) : n,m = map(int, data.pop(0).split()) arr = [list(map(int, list(x))) for x in data] # 방향 directions = [[-1,0],[0,-1],[1,0],..
백준2468 - 안전 영역 (DFS) Python
https://www.acmicpc.net/problem/2468 해당 문제는 주어진 2차원 배열에서, 수심에 따른 안전 지역의 갯수를 구한 뒤 최댓값을 출력하는 문제다. 구역을 나누는 방식에는 DFS 알고리즘이 익숙하기 때문에 해당 알고리즘으로 접근했다. 풀이 방식은 다음과 같다. 먼저 수심에 따른 안전지대의 갯수를 구하는 것이므로, 수심의 범위를 제한하는 과정이 필요하다. 그리고 수심의 범위는 2차원 배열이 가진 최솟값과 최댓값 사이이기 떄문에, 해당 이차원 배열에서 나올 수 있는 수심 즉 깊이는 2차원 배열이 가진 최솟값 이상 최댓값 이하이기 때문에, 아래와 같이 미리 변수를 선언해두었다. n = int(data.pop(0)) matrix = [list(map(int, v.split())) for ..