티스토리

냥인의 블로그

검색하기

블로그 홈

냥인의 블로그

nyang-in.tistory.com/m

냥인 님의 블로그입니다.

구독자: 2

방명록 방문하기

728x90

주요 글 목록

[백준] 15649. N과 M (1) (자바스크립트/javascript/js/node.js/백트래킹) 문제를 풀기 위한 아이디어 이 문제는 한마디로 순열을 구하는 것이다. 이전에 내가 포스팅했던 순열 알고리즘을 써도 되지만, 이 문제는 백트래킹 알고리즘 유형에 있던 문제이기 때문에 한번 백트래킹으로 풀어보았다. * 백트래킹 이란 ? 모든 조합의 수를 다 살펴보되 (완전탐색) 단 조건이 만족할 때에만 탐색하는 방법을 말한다. 쉽게 말해 해를 찾는 도중 해가 아닌 것 같으면 되돌아가서 해를 찾는 것이다. 완전탐색을 하는 방법으로는 DFS, BFS가 있다. 백트래킹은 DFS에서 효율적인 방법이다. 왜냐하면 DFS는 깊이 우선 탐색이므로 갈 수 있는 최대 깊이까지 갔다가 돌아온다. 우리는 끝까지 탐색하지 않아도 중간에 조건에 부합하지 않는 경우가 있어서 현재 경로가 잘못된 것임을 알 수 있는 경우가 종종 있다... 공감수 0 댓글수 0 2021. 7. 15.
[백준] 13305. 주유소 (자바스크립트/javascript/js/node.js/그리디 알고리즘/탐욕법) 문제를 풀기 위한 아이디어 문제가 장황하지만, 결국 생각해야할 포인트는 단순하다. 가장 최저가인 곳에서 기름을 구매해서 제일 오른쪽 도시(도착점)까지 가면 되는데, 그 최저가인 지점까지 도착하기 전까지는 그 전에 있는 곳 중 최저가에서 구매를 해야 한다. 이게 계속 반복된다. 생각을 조금 전환시키면, 매 순간 순간마다 최저가를 갱신시키면 된다. 현재 최저가가 지금 머무르고 있는 곳의 가격보다 비싸다면 최저가가 갱신되는 것이다. 그렇게 해서 최저가와 갈 거리를 곱해서 총 비용에 누적시키면 된다. 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.readFileSync("예제.txt").toString().split("\n"); let cost = Big.. 공감수 0 댓글수 0 2021. 7. 14.
[백준] 1541. 잃어버린 괄호 (자바스크립트/javascript/node.js/그리디 알고리즘) 문제를 풀기 위한 아이디어 어려운 문제는 아니다. 그러나 제출했을 때 오류가 나서 다른 방법을 찾느라 좀 번거로웠던 문제이다. 일단 근본적으로 문제를 해결하는 방법은, 최솟값이 나오기 위해서는 마이너스를 최대한 크게 해서 빼는 것이 최솟값이 되기 때문에, 마이너스가 나타나면 마이너스 뒤에서 괄호 "("로 묶기 시작하여 또 다른 마이너스를 만나기 직전에 ")"를 추가하는 방법이다. 예제의 경우 55-50+40 이라면 55-(50+40) 이렇게 하는 것이다. 그렇게 하여 주어진 식을 배열로 다 나누어서 마이너스가 나타나면 "-("로 바꾸고 이런식으로 푼 다음에 마지막에 문자열로 합치고 eval을 이용해서 식을 계산했는데 처음에 런타임에러(SyntaxError)가 나와서 eval은 아무래도 좋은 방법이 아닌 .. 공감수 0 댓글수 0 2021. 7. 14.
[백준] 12865. 평범한 배낭 (자바스크립트/node.js/javascript/동적 계획법/동적 프로그래밍/다이나믹 프로그래밍) 문제를 풀기 위한 아이디어 동적 프로그래밍의 대표적인 유형 중 하나인 0/1 배낭 문제이다. (배낭문제에 대한 포스트는 지난 게시글에 올렸으니 참고하실 분들은 참고하시면 됩니다.) 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let knapsack = fs.readFileSync("예제.txt").toString().split("\n"); const N = Number(knapsack[0].split(" ")[0]); const K = Number(knapsack[0].split(" ")[1]); knapsack = knapsack.map((element) => element .trim() .split(" ") .map((value) => Number(value)) ); .. 공감수 0 댓글수 0 2021. 7. 13.
[동적 프로그래밍] 0/1 배낭 문제 (자바스크립트/javascript/js/백준 12865) 오늘은 동적 프로그래밍 문제 중 대표적인 유형인 0/1 배낭 문제에 대해 알아보겠습니다. 물건의 개수 N이 주어지고, 배낭이 최대로 버틸 수 있는 무게 K가 주어지고 각 물건의 무게와 가치가 주어질 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다. 문제가 0/1 배낭 문제라고 불리는 이유는 물건을 쪼개서 넣을 순 없고 물건을 넣거나/안넣거나 둘 중 하나의 선택만 할 수 있기 때문입니다. 예를 들어 물건의 개수가 4개, 배낭의 무게는 7이고 각 물건의 무게와 가치가 다음과 같다고 합시다. 물건의 개수가 4개밖에 되지 않기 때문에 브루트포스(완전탐색)로 구하더라도 짧은 시간내에 금방 구할 수 있으나 물건의 개수가 조금만 늘어나더라도 따져보아야할 경우의 수는 기하급수적으로 늘어나기 때문에 .. 공감수 0 댓글수 0 2021. 7. 13.
[백준] 1912. 연속합 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍) 문제를 풀기 위한 아이디어 1. 직전까지의 부분합 + 현재 가리키고 있는 수 2. 현재 가리키고 있는 수 를 비교하여 더 큰 값을 부분합으로 저장한다. 즉, 지금까지 연속해서 더한 부분합+현재 가리키고 있는 수와 그냥 현재 가리키고 있는 수를 비교했는데 현재 가리키고 있는 수가 더 크다면 미련없이 이전 수들을 버리고 새롭게 시작하여도 OK라는 것이다. 예제 1을 가지고 예를 들어보면, [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]에서 dp[7]까지는 쭉 더하다가 8번째 수인 12를 만났을 때 -14 + 12 vs 12를 비교해서 12가 더 크기 때문에 이전 값을 다 버리고 12부터 시작하는 것이다. 그렇게 해서 구한 모든 dp 값 중 최댓값을 출력하면 된다. 내가 구현한 코드 (자바.. 공감수 0 댓글수 0 2021. 7. 13.
[알고리즘] LCS(Longest Common Subsequence, 최장 공통 부분 수열) (자바스크립트/javascript/js/동적계획법/동적 프로그래밍 /다이나믹 프로그래밍) (백준 9251) LCS(Longest Common Subsequence, 최장 공통 부분 수열) 이번 시간에는 LCS(Longest Common Subsequence, 최장 공통 부분 수열)에 대해 알아보겠습니다. 지난 시간에 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)에 대한 문제를 백준에서 풀어보았는데요. (이전 포스팅 참조) 이번 에는 LCS에 대해 알아보겠습니다. LCS, 최장 공통 부분 수열이란 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. 예를 들어, CAPCAK와 ACAYKP의 LCS는 ACAK가 됩니다. (이 때 꼭 문자열이 연속해야 할 필요는 없습니다.) 이 문제를 풀어보는 방법은 다음과 같습니다. 우선 ACAYKP와.. 공감수 1 댓글수 0 2021. 7. 13.
[백준] 11054. 가장 긴 바이토닉 부분 수열(자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍) 문제를 풀기 위한 아이디어 앞선 문제 [11053. 가장 긴 증가하는 부분 수열] 에서 조금만 창의적으로 생각하면 풀 수 있는 문제이다. 이 문제는 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열의 합을 구해서 최댓값을 구하면 되는 문제이다. 나는 최대한 헷갈리지 않기 위해서 가장 긴 증가하는 부분 수열을 구해서 값을 저장할 공간을 increaseDP라는 배열을 만들어 값을 저장했고, 가장 긴 감소하는 부분 수열을 구해서 값을 저장할 공간은 decreaseDP라는 배열을 만들어 값을 저장했다. increaseDP[1] = 1 decreaseDP[N] = 1을 저장한다. 주어진 수열은 numbers라는 배열에 저장한다. (나는 numbers의 0번째 인덱스에 값을 추가해주었다. 뒤에서 반복문에.. 공감수 0 댓글수 0 2021. 7. 12.
[백준] 11053. 가장 긴 증가하는 부분 수열 (자바스크립트/javascript/node.js/동적계획법/동적 프로그래밍/다이나믹 프로그래밍) 문제를 풀기 위한 아이디어 일단 "가장 긴 증가하는 부분 수열" 이라는 것은 주어진 수열 내에서 공차, 공비 이런 것은 신경쓰지 않고 단순히 증가하는 양상만 보았을 때 어떤 부분 수열(쉽게 말해서 부분 집합)이 가장 긴 가를 따지는 것이다. 우선 dp값을 저장할 배열을 주어진 수의 길이인 N 사이즈에 맞게 만들고 초기 값을 모두 1로 채워준다. dp[N]에는 N까지의 배열에서 가장 긴 증가하는 부분 수열의 길이가 저장될 것이다. 이 때 초기값을 1로 채워주는 이유는, 최소한 자기 자신은 다 가지고 있기 때문에 1로 채워주는 것이다. 그리고 문제에서 주어진 수열을 numbers라는 배열에 저장하고, 각 numbers를 반복문을 돌며 자기 자신보다 작은 값을 세야 한다. numbers = [100, 200,.. 공감수 1 댓글수 0 2021. 7. 12.
[백준] 2156. 포도주 시식(자바스크립트/javascript/node.js/js/다이나믹프로그래밍/동적프로그래밍/동적계획법) 문제를 풀기 위한 아이디어 dp 배열을 만든다. dp[N]에는 포도주의 개수가 N개일 때 최댓값이 저장될 것이다. dp[1] = wine[1] (포도주가 1개밖에 없을 때에는 무조건 1개의 포도주를 마시는게 최댓값이다.) dp[2] = wine[1] + wine[2] (포도주가 2개밖에 없을 때에는 무조건 2개의 포도주를 모두 마시는게 최댓값이다.) dp[3] = (wine[1] + wine[2] , wine[2] + wine[3] , wine[1] + wine[3]) 이 3가지 경우에서 가장 큰 값이 최댓값이 된다. (연속해서 3잔을 먹을 순 없기 때문에) dp[4]부터는 dp[N]을 어떻게 구할 수 있을까? 위의 그림이 모든 것을 설명해준다. 즉 저 위의 3가지 경우 중 최댓값이 dp[N]이 된다. .. 공감수 0 댓글수 0 2021. 7. 9.
[백준] 10844. 쉬운 계단 수 (자바스크립트/javascript/js/node.js/동적프로그래밍/동적계획법/다이나믹프로그래밍) 문제를 풀기 위한 아이디어 다이나믹 프로그래밍 문제는 언제나 점화식을 세우는 것이 중요하다. 이번 문제는 dp에서 2차원 배열을 이용해서 저장하는 것을 배울 수 있었던 문제였다. 우선 0으로 시작하는 수는 없다고 했기 때문에, n=1인 경우 1,2,3,4,5,6,7,8,9 = 9가지 경우가 나온다. n=2인 경우를 생각해보자. (10,11) (21,23) .... (98)로 다 합치면 17가지 경우가 나온다. 즉 앞의 수가 0이면 뒤에 올 수 있는 수는 1밖에 존재하지 않는다. 만약 앞의 수가 1부터 8이라면 각각 두개씩 존재할 수 있다. 만약 앞의 수가 9라면 뒤에 올 수 있는 수는 8밖에 존재하지 않는다. 이를 염두해두어야 한다. dp[n][i]를 n자리수 이면서 i로 끝나는 경우라고 한다면, 우선 .. 공감수 3 댓글수 2 2021. 7. 9.
[백준] 2579. 계단 오르기 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍) 문제를 풀기 위한 아이디어 우선 dp배열을 만든다. 이 배열의 dp[n]에는 계단이 n개일 때 얻을 수 있는 점수의 최댓값이 저장될 것이다. 그리고 입력값으로 주어진 각 계단마다의 점수들을 stairs라는 배열에 저장한다. 이 때 계단 또한 1번째 계단이면 stairs[1]로 생각할 수 있게끔 stairs[0]에도 값을 넣어주면 편하다. (배열의 인덱스로 헷갈리지 않기 위함) dp[1] = stairs[1] : 계단이 1개일 때에는 계단 1개를 무조건 밟는 것이 최대 점수이다. (그리고 어차피 도착계단을 무조건 밟아야 하기 때문) dp[2] = dp[1] + stairs[2] : 계단이 2개일 때에는 계단 2개 다 무조건 밟는 것이 최대 점수이다. (계단을 연속해서 2개 밟는 것 까지는 괜찮다.) dp[.. 공감수 0 댓글수 0 2021. 7. 8.
[백준] 1463. 1로 만들기 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹프로그래밍/동적프로그래밍) 문제를 풀기 위한 아이디어 Bottom-up 방식으로 접근해본다. dp 배열을 만든다. dp[n]에는 숫자 n이 1이 되기 위해 연산한 최소 횟수가 저장될 것이다. dp[1] = 0 이다. (1은 아무짓도 안해도 1이 되기 때문에) dp[2]는 2가 되기 전에 1에다 +1을 해야 나올 수 있는 수 이기 때문에 dp[1] + 1 = 1이 된다. (+1이라는 것은 연산횟수가 한 번 더해지기 때문에 더한 것이다.) dp[3]은 3이 되기 전에 이 수가 2였을 수도 있고 1이였을 수도 있다. 즉, 2에다 1을 더해도 3이 되고, 1에다 3을 곱해도 3이 된다. 즉 dp[3] = (dp[2] + 1 , dp[1] + 1) 중 최솟값이 된다. 그럼 dp[4]부터는 어떻게 구할 수 있을까? dp[4]는 2로 나누어 .. 공감수 2 댓글수 0 2021. 7. 8.
[백준] 1932. 정수 삼각형 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍) 문제를 풀기 위한 아이디어 삼각형의 각각 n번째 줄을 행이라고 하고 그 행에서 하나의 요소들을 열이라고 둔다면 같은 행 안에서 가장 첫 열과 가장 끝 열을 제외하고 중간에 있는 요소들은 겹친다. 즉 중복해서 더해진다. 예를 들면 0번째 행, 1번째 행은 중간에 있는 요소가 없기 때문에 안 겹치지만 2번째 행부터는 가장 첫 열인 8과 가장 끝 열인 0을 제외하고 중간에 있는 1은 그 전 행의 3과도 더해질 수 있고 8과도 더해질 수 있다. 지금 문제는 이 중에서 최댓값을 구하라고 했기 때문에 중복해서 더해지는 요소는 두 가지 경우 중 최댓값만 저장하면 된다. 이를 그림으로 표현하면 다음과 같다. 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.read.. 공감수 0 댓글수 0 2021. 7. 5.
[백준] 1655. 가운데를 말해요 (자바스크립트/javascript/node.js/힙정렬/우선순위 큐) 문제를 풀기 위한 아이디어 힙을 이용해서 중간값을 구하는 문제이다. 이전에 블로그 포스팅으로 했었던 힙으로 중앙값찾기를 잘 연습했던 터라 이 문제는 빠르게 잘 풀 수 있었다. 다만 연습했었을 때에는 최소힙과 최대힙의 크기가 같을 때 최소힙에서 가장 작은 값, 최대힙에서 가장 큰 값을 더해서 2로 나눈 값이 중앙값이 되었다면 이번 문제에서는 둘 중 최솟값을 중앙값으로 지정하여야 한다. 이는 자바스크립트의 Math.min 메소드를 통해 쉽게 구현했다. (제 블로그를 검색을 통해 들어온 분들은 아래의 게시글에 설명이 되어있으니 참고하시면 됩니다.) https://nyang-in.tistory.com/155 [자바스크립트 자료구조] 힙(heap) - 연습문제 일련의 숫자에서 중앙값 찾기 중앙값이란 어떤 배열을 .. 공감수 0 댓글수 0 2021. 7. 2.
[프로그래머스] N으로 표현 (자바스크립트/javascript/js/동적계획법/동적프로그래밍/다이나믹프로그래밍) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제를 풀기 위한 아이디어 이 문제는 N을 1번 쓰는 경우, N을 2번 쓰는 경우 , .... , N을 8번 쓰는 경우까지 따져보아야 한다. 문제에서 N이 8보다 크다면 -1을 출력하라고 했으므로 N을 8번 쓰는 경우까지 구해보고 나오지 않는다면 -1을 출력하면 된다. use라는 9 크기의 배열을 만든다. (9인 이유는 N을 8번 쓰는 경우까지 구할 것인데 배열의 인덱스가 0에서 시작함을 감안하여 더 직관적으로 생각하기 위해서 N을 1번 쓰는 경우를 use[1]에 저장하고, N을 2번 쓰는 경우를 use[2]에 저장하고, .... 공감수 2 댓글수 0 2021. 7. 2.
[백준] 1149. RGB거리 (자바스크립트/javascript/js/node.js/동적 프로그래밍/다이나믹 프로그래밍 / 동적계획법) 문제를 풀기 위한 아이디어 규칙이 복잡해보이지만 숫자를 대입하여 생각해보면 결국 바로 인접한 집끼리만 다른 색이면 된다는 것이다. 일단 주어진 각 집을 빨강,초록,빨강으로 칠하는 비용들을 2차원 배열에 저장한다. input = [ [26, 40, 83], [49, 60, 57], [13, 89, 99] ] 그 다음으로는 첫번째집을 R로 칠한 경우 / 첫번째 집을 G로 칠한 경우 / 첫번째 집을 B로 칠한 경우를 모두 다 따져주면 된다. 이를 점화식으로 세우면, 두번째 집부터는 다음과 같은 점화식이 성립한다. input[i][0] = min(input[i-1][1], input[i-1][2]) + input[i][0] input[i][1] = min(input[i-1][0], input[i-1][2]) +.. 공감수 0 댓글수 0 2021. 7. 2.
[백준] 9461. 파도반 수열 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍) 문제를 풀기 위한 아이디어 동적 프로그래밍 유형이 다들 그러듯이 점화식만 잘 세우면 된다. 점화식은 다른 분들의 코드를 보니까 여러 점화식이 나올 수 있는데 나는 그림을 보고 바로 유추할 수 있는 점화식을 사용했다. P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2 P(5) = 2 P(6) = 3 P(7) = 4 P(8) = 5 까지는 값을 미리 넣어놓고, P(9)부터는 P(N) = P(N-5) + P(N-1)을 사용했다. 사실 P(1)~P(3)까지만 넣어놓고 P(4)부터 P(N) = P(N-2) + P(N-3)을 쓰는 것이 더 좋은 방법인 것 같긴 하다. 하지만 나는 그림을 보고 예를 들어 P(9) = P(4) + P(8)의 합이라고 딱 그림에서 보기 쉬웠기 때문에 이렇게 점화식을 세웠다.. 공감수 0 댓글수 0 2021. 7. 1.
[알고리즘] 동적계획법 (동적프로그래밍, 다이나믹 프로그래밍) (자바스크립트/javascript/js) 동적계획법이란? 큰 문제를 한 번에 해결하기 힘들 때 작은 문제로 나누어 푸는데, 이 때 이전에 계산한 값을 저장해두었다가 다시 사용하는 것이 핵심이다. 큰 문제를 작은 문제로 분할하여 푼다는 점에서 분할정복 알고리즘과 유사하지만, 한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다르다. 동적계획법이 필요한 이유 그렇다면 왜 동적계획법이 필요한 것일까? 피보나치 수열을 예를 들어보자면, 점화식은 F(n) = F(n-1) + F(n-2)가 된다. 이는 간단하게 재귀함수만으로 구현할 수 있지만, 비교적 그렇게 어마어마하게 크지 않은 수인 50만 생각해보더라도 50을 구하기 위해서 불필요한 재귀가 일어나게 되어 엄청나게 많은 연산이 요구된다. 위의 그림에서도 .. 공감수 0 댓글수 0 2021. 7. 1.
[백준] 1904. 01타일 (자바스크립트/javascript/js/동적계획법/다이나믹프로그래밍/동적프로그래밍) 문제를 풀기 위한 아이디어 다이나믹 프로그래밍 유형은 점화식을 세우는 것이 가장 중요하다. 이 문제의 점화식은 타일의 개수가 N개일 때 만들 수 있는 N자리수 이진수의 모든 개수를 T(n)이라 하면, T(n) = T(n-2) + T(n-1)이다. 다이나믹 프로그래밍을 푸는 방법에는 Top-down 방식과 Bottom-up 방식이 있는데, 처음에 이문제를 Top-down 방식으로 푸니까 stack이 계속 초과되었다고 나와서 Bottom-up 방식으로 반복문으로 풀었다. 내가 작성한 코드 (자바스크립트) function solution(N) { const memo = new Array(); memo[1] = 1; memo[2] = 2; for (let i = 3; i 공감수 0 댓글수 0 2021. 7. 1.
[백준] 1003. 피보나치 함수 (자바스크립트/javascript/js/동적계획법/다이나믹프로그래밍/동적프로그래밍) 문제를 풀기 위한 아이디어 피보나치 수열의 n번째 숫자는 n-2번째 수와 n-1번째 수의 합이 된다. 피보나치 수열을 재귀함수로만 풀 수도 있지만, 이렇게 하게 되면 비교적 작은 수더라도 실행횟수가 어마어마해진다. 예를 들어 fibonacci(5) 함수를 통해 피보나치 수열의 5번째 수를 구하려고 한다면, 아래의 그림과 같다. fibonacci(5) = fibonacci(4) + fibonacci(3) 이기 때문에, fibonacci(4)는 또 재귀를 부르고 fibonacci(3)도 재귀를 부른다. 이렇게 하면 안좋은 점이 2같은 경우에 3번이나 중복되고 있어 연산회수가 불필요하게 많아지고 있다. 5여서 망정이지 50번째 수만 되더라도 재귀를 쓰면 반복횟수는 어마어마해진다. 따라서 이미 구해놓은 값은 저.. 공감수 0 댓글수 0 2021. 7. 1.
[백준] 2960. 에라토스테네스의 체 (자바스크립트/javascript/js) let fs = require("fs"); let input = fs.readFileSync("예제.txt").toString().split(" "); const N = Number(input[0]); const K = Number(input[1]); const numbers = new Array(Number(input[0]) + 1); let primeNumber; const count = []; for (let i = 2; i < numbers.length; i++) { numbers[i] = i; } for (let i = 2; i 공감수 0 댓글수 0 2021. 7. 1.
[프로그래머스] 디스크 컨트롤러 (자바스크립트/js/javascript/우선순위큐/힙) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제를 풀기 위한 아이디어 이 문제는 결국 현재 시간에서 시작할 수 있는 작업 중에 가장 작업 시간이 짧은 것을 우선적으로 처리하면 된다. 일명 SJF(Shortest Job First) 방식이라고 할 수 있다. SJF 들어본 적은 있는데 이걸 이렇게 접할 줄은 .... 일단 먼저 정렬한다. 정렬하는 순서는 jobs[index]라고 치면 jo.. 공감수 0 댓글수 0 2021. 6. 30.
[프로그래머스] 여행경로 (자바스크립트/javascript/js) 문제출처: https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 내가 작성한 코드 function solution(tickets) { const answer = []; const DFS = (start, tickets, path) => { const newPath = [...path, start]; if (tickets.length === 0) { answer.push(path);.. 공감수 0 댓글수 0 2021. 6. 28.
[프로그래머스] 짝지어 제거하기 (자바스크립트/javascript/js) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12973?language=javascript 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 문제를 풀기 위한 아이디어 처음에는 그냥 반복문을 돌면서 index를 가지고 index와 index+1이 같은지 비교한 후 같다면 둘을 잘라내고 index는 처음부터(0부터) 다시 반복문을 돌렸었다. index와 index+1이 같지 않다면 index를 증가시키는 방법으로 풀었었다. 그러나 시간초과가.. 공감수 0 댓글수 0 2021. 6. 24.
[프로그래머스] 오픈채팅방 (자바스크립트/js/javascript) 문제출처: https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 문제를 풀기 위한 아이디어 문제 설명은 장황하지만 결국 포인트는, 닉네임을 먼저 확정짓고 그 다음에 맞는 유저 아이디의 닉네임을 불러오기만 하면 된다. 모든 record를 반복문으로 돌며 계속해서 유저 아이디에 맞는 닉네임을 갱신해주어서 먼저 닉네임을 확정짓는다. 이 경우 Leave인 경우는 닉네임이 바뀌지 않으므로 신경쓸 필요가 없다. 또 recor.. 공감수 0 댓글수 0 2021. 6. 24.
[프로그래머스] 124 나라의 숫자 (자바스크립트/javascript/js) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12899?language=javascript# 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 문제를 풀기 위한 아이디어 124 나라에서는 1 →1, 2 → 2, 3 → 4 인 것을 생각하고 풀어야 한다. 주어진 수를 우선 3으로 나눈다. 이 때 3으로 나누어 떨어지는 수는 몫에서 -1을 하고 나머지를 3으로 두어야 한다. 그렇게 해서 나눈 몫과 나머지가 1,2,3이 될 때까지 재귀함수를 돌려서 문자열로 합쳐주면 된다. function solution(n) { const getOneTwoFourNumber = (number) => { let numberString = ""; .. 공감수 0 댓글수 0 2021. 6. 24.
[프로그래머스] 문자열 압축 (자바스크립트/ javascript/ js) 문제출처: https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제를 풀기 위한 아이디어 일단은 1개부터 총 문자열 길이의 절반까지 모두 잘라서 비교해본다. (이 때 문자열 길이의 절반까지로 하는 이유는 만약 문자열의 길이가 5개라면 2개까지는 잘라도 되지만 3개부터, 즉 과반수를 넘어가면 자르는게 의미가 없기 때문에 범위를 좁혀서 효율성을 더 높일 수 있다. 그러나 문자열의 길이가 1인 경우도 생각해야 .. 공감수 0 댓글수 0 2021. 6. 23.
[프로그래머스] 구명보트 (자바스크립트/ javascript/ js) 문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제를 해결하기 위한 아이디어 이 문제는 무인도에 갇힌 사람을 나타내는 people 배열이 최대 5만명이기 때문에 효율적인 방법으로 코드를 작성해야 한다. 처음에는 알고리즘다운 생각을 제대로 하지 못해서 이중 for문으로 가능한 경우의 수를 모두 도는 방법을 생각했는데, 이 문제는 효율성 점수도 있기 때문에 그렇게 해서는 .. 공감수 0 댓글수 0 2021. 6. 23.
[프로그래머스] 타겟 넘버 (자바스크립트/javascript/js) 문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀기 위한 아이디어 주어진 numbers의 숫자들을 더하거나 빼야하므로 예제를 그림으로 나타내면 다음과 같다. 예제에서는 숫자가 5개 였지만 depth를 5까지 그림으로 표현하기에는 너무 가독성이 떨어져서 4 depth까지만 표현했다. 이렇게 numbers라는 배열에 들은 각각의 값들은 +이.. 공감수 0 댓글수 0 2021. 6. 23.

728x90

문의안내

티스토리
로그인
고객센터

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