문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 정답 풀이 그래프 최단 경로 ? bfs 알고리즘을 사용해야 되는 것은 모두 다 알거다. 그런데 구현하기가 어려웠는데, 그 이유는 함수화 하지 않아서 solution 기본 함수가 복잡해진 탓이라고 생각한다.  또, 회전하는 경우를 가로 => 세로 인 것과 세로 => 가로를 구분해줘야 한다.  또 이미 방문한 위치는 Set 객체를 이용하면 된다. 정답 코드function solution(boa..

문제 출처 https://www.acmicpc.net/problem/12865 정답 풀이 풀이 보니까, dp로는 유명한 문제라는데 아직도 못 푸는 나 자신 머리 한대 때리고 시작하자.  이해하면 코드는 간단하나, 이해하기 생각보다 빡셌다. 다른 분들의 블로그를 봐도 잘 이해가 안갔고, 그래서 내가 이해한 방식대로 글을 작성해볼 예정이다.  ## dp 그래프 생성 아래와 같이 2차원 그래프 dp를 생성해줄 것이다. 세로 의미: 각 물건의 무게와 가치 가로 의미: 준서가 버틸 수 있는 무게  그렇다면 dp 그래프의 의미는 어떻게 될까? 각 물건을 넣고, 안넣고에 따라서 + 준서의 배낭 각 무게에 따라의 '가치'를 계속 update 해줄 것임. (이해가 안가도 아래 쭉 예시를 읽어보자 !) ## 초기화 아래 ..

문제 출처 https://www.acmicpc.net/problem/5582 문제 풀이  dp 2차원 그래프를 그린다. str1 = 'GBCDFE'str2 = 'ABCDEF'인 상황이다.  각각 str의 길이를 이렇게 설정해주자. let n =  str1.length let m = str2.length  우리는 dp를 이용할 건데 dp 2차원 그래프를 생성하자. 세로:n+1  ,가로: m+1 길이를 가진 그래프일 것이다  모두 0으로 채울 것이다.  아래 그림과 같이 특히 idx 0은 무조건 0인데 무슨 의미일까? ''과 'ABCDEF'를 비교하면, 같은 부분이 없고, 'GBCDFE'와 ''를 비교하면, 같은 부분이 없다는 의미다.  아래 분홍색 부분은 어떤 것을 뜻하는가? 'GBCDFE'에서의 'GBC..

문제 출처 https://www.acmicpc.net/problem/10775 정답 풀이  사람들 천재야? 어떻게 이런 생각을 했는지 싶다 그리디 참 쌈박한 문제다. 인정 ! - 그리디 알고리즘 - 유니온 파인드 자료구조 를 활용해서 풀 수 있다.  각 게이트는 비행기를 수용할 수 있고, 가장 큰 번호의 게이트에 비행기를 도킹시켜야 최대한 많은 비행기를 도킹시킬 수 있다.  1. Union-Find 자료구조- find(x): x가 속한 집합의 대표자를 찾는다. 경로 압축을 사용하여 효율적으로 찾는다. - union(x,y): x와 y를 같은 집합으로 합친다.   2. 그리디 - find(gate) : 각 비행기에 대해, 해당 비행기가 도킹할 수 있는 가장 큰 번호의 게이트를 찾는다 - union(avai..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 정답 풀이 DFS 알고리즘을 활용해서 미로에서 탈출하는 경로를 찾는 문제. - k번의 이동 - 사전순으로 가장 빠른 경로 반환  1. 맨해튼 거리 계산 - 출발점에서 목표점까지의 맨해튼 거리 계산 - 만약, k이동 횟수가 이 거리보다 작거나, 맨해튼 거리와 k의 홀짝성이 다르면 도달 할 수 없으므로 => impossible  2. dfs - 스택을 사용하여 dfs 구현 - 후입선출방식, ..

문제 출처 https://www.acmicpc.net/problem/1991 정답 코드 1const input =require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const n = Number(input.shift())function solution(n, arr){ const preOrderArr = []; const inOrderArr = []; const postOrderArr = []; const tree = {}; for(let i=0; i { if(node === '.') return; let [left, right] = tree[node] ..

문제 출처 https://www.acmicpc.net/problem/1300 정답 풀이  일단 이 논리를 알고가자 주어진 배열에서 8이하인 수가 몇개 있을까?   결론부터 말하면 8이라는 숫자를 각 배열의 idx값으로 나는 몫을 다 더한 개수가 된다. idx가 1인 배열을 봐보자. 8/1을 하면 몫이 8이 된다. 그런데 애초에 가로 배열 크기가 4가 최대니까 값이 4가 된다. ...idx가 4인 배열을 봐보자. 8/4를 하면 몫이 2가 된다. 실제로 8이하인 수의 개수는 4와 8 두개이다.   왜 이런 논리가 들어맞는걸까? 사실 각 idx로 나눠준 것은 각 가로 배열의 첫번째 숫자를 의미한다. idx === 배열 첫번재 숫자가 같다.   그리고, 해당 가로 배열을 보면, 해당 숫자만큼 계속 커지는 규칙을..

문제 출처 https://www.acmicpc.net/problem/2437 정답 풀이 이건 문제 푸는 아이디어를 생각하기 정말 어려웠을 것 같다. 나도 여러 블로그를 통해 이해가 됐고, 만약 이런 방식으로 설명이 되어 있었다면 ,이해가 좀 더 수월할 수 있었을 것 같은 방식으로 이야기 해보려고 한다.  [1,1,2,3,6,7,30] 배열이 주어졌다고 가정하자. 이해하기 쉽게 중간부터 흐름을 따라가보자.  1,1,2,3 으로 표현할 수 있는 최솟값은 1이다. 최댓값은 7이다.  (1 + 1 + 2 + 3)   그 다음 숫자 6을 넣으려고 할 때, 6이 내포하는 의미가 무엇이겠는가? 적어도 6을 표현할 수 있고, 이전 숫자들로 표현할 수 있었던 값 7과 더한다면 최대로 13을 표현할 수 있다는 뜻이 된다...

문제 출처 https://www.acmicpc.net/problem/11000 문제 풀이 생각의 전환이 필요한 문제였다.  - 일단 시간들을 오름차순으로 정렬하자 - 정렬한 시간들을 탐색한다.   - 그때 start의 시간이라면 방이 하나 필요하다 "+1" 는 뜻   - 그때 end의 시간이라면 방을 하나 반납한다 "-1" 는 뜻  - 매순간 방을 최대로 쓴 값이 답이 된다.     - 왜냐하면 이미 우리는 강의실을 최적으로 정렬을 해놨기 때문에       그때 필수적으로 써야 했던 방의 개수가 최소의 강의실을 사용하는 것이 된다. 정답 코드 let fs = require('fs');let [N, ...input] = fs.readFileSync('/dev/stdin').toString().trim()...

문제 출처 https://www.acmicpc.net/problem/12015 정답 풀이  참 좋은 문제이고, 기가막힌 방법이다. 문제에서 가장 긴 수열 알고리즘의 길이를 구하라고 했으니,  - LIS 알고리즘을 활용하기 - LIS 알고리즘을 돕는 헬퍼 이진탐색 활용하기  LIS 알고리즘의 푸는 아이디어만 간단하게 공유하면 될 것 같다.  ### LIS 알고리즘 수열 = {10,20,10,30,20,50} 인 경우로 보자.  - 먼저 배열에 10을 넣는다.   - 새로 넣어야 하는 수는 20이다 - 배열의 마지막 값인 10과 비교했을 때 20이 더크니 배열에 추가한다.   - 새로 넣어야 하는 수는 10이다- 배열의 마지막 값인 20과 비교했을 때 10이 더 작다. - 배열에서 10보다 크지만 가장 작은..