문제 출처 https://www.acmicpc.net/problem/2293 정답 풀이 알아보니, 이 문제는 js언어로 메모리 초과가 나는 문제인 것 같다.  이 분의 풀이를 보면 이해가 더 쉬울 것 같다. https://www.youtube.com/watch?v=LBOQikSpfNg 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,k] = input.shift().split(' ').map(v => +v); const arr = []; for(let i=0; i틀린 코드 완전탐색의 방법밖에 떠오르지 않았다.. 메모리 초과... 가 될 걸 알았지만 작성한 이유는, 요즘에는 ..

문제 출처 https://www.acmicpc.net/problem/2638 정답 풀이 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(v => +v);const arr = [];for (let i = 0; i +v));}function solution(n, m, graph) { let answer = 0; bfs(n, m, graph); // 초기 외부 공기(-1)로 표시 while (true) { let hasCheese = false; // 치즈가 남아있는지 확인 l..

문제 출처 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/16234 정답 풀이 bfs 알고리즘을 활용했다.  - 일단 주어진 board의 전체를 돈다.   - 이때 한번 방문한 위치는 안간다.  - 모든 board를 다 돌았을 때 그 어떤 값도 변경되지 않는다면 반복문에서 break를 한다.  - 한번 방문한 곳에서 bfs 함수를 돌린다.    - 이때 arr 배열에 조건에 맞는 (L 이상 R이하 차이) 위치들을 push 한다.  - arr의 위치들의 board 값을 다 더하고 평균을 내서 새롭게 board에 값을 넣어준다.  정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')cons..

실수1. split(' ') 작성 안함.백준에서는 치명적인 실수였다.  실수2. 변수의 재사용 (x,y, i, d) 진짜 이런 실수는 하면 안된다. 매개변수를 i,j 로 받아놓고, 4가지 방향으로 뻗어줄 때 변수를 i로 작성했었다.  이제 매개변수로 받는 값은 x,y로 해야한다. 또 방향 전환 하는 변수는 d로 설정하자. 이래야 다음에는 실수를 하지 않을 것 같다.  실수3. queue의 초기값에 대하여queue의 초기값에 대하여 설정해야 할 것들 checked  나 arr에 push 하기 이런건 해당 부분에서 처리해주자. 실수4. checked - checked를 true로 설정해야 한다. 이걸 계속 false 로 했었음;;

문제 출처 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://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 효율성을 생각하지 않는다면, 아래 코드가 간결할 수 있겠다. function solution(words, queries) { let answer = new Array(queries.length).fill(0) queries.forEach((query, idx) => { let q = '^'+ query.replaceAll('?','.') + '$' ..

문제 출처 https://www.acmicpc.net/problem/9251 정답 풀이 - 두 문자열의 공통 부분 수열 중 가장 긴 부분 수열을 찾는 것. - 부분 수열은 원래 문자열에서 문자를 순서를 유지한 채 일부를 선택하여 만든 문자열이다.  DP 접근 방법 - 두 문자열의 각 문자 쌍을 비교하면서 최장 공통 부분 수열을 점진적 계산 - 2차원 배열 사용 - 각 셀 DP[i][j]는 첫번째 문자열의 첫 i개 문자와 두번째 문자열의 첫 j개 문자를 비교했을 때의 LCS 길이를 나타낸다.  테이블 초기화 - DP[i][0]와 DP[0][j]는 0을 초기화한다. 왜냐하면 공백과 어떤 문자열을 비교하면 공통 부분 수열의 길이는 항상 0이다.  점화식 - str[i-1] 과 str[j-1]이 같으면 dp[i..

아래 세가지 이유에 대해 알아보자.  - 그래프 탐색에서 DFS와 BFS 차이점- DFS: 스택, BFS:큐를 사용하는 이유 - 각 기법을 언제 사용하는지  ## DFS와 스택 dfs는 그래프 탐색 시 "한 방향으로 끝까지 탐색하고, 더이상 갈 곳이 없으면 되돌아와서 다른 경로를 탐색하는" 방법이다.이 방법은 재귀적인 탐색을 요구한다. ### 스택을 사용하는 이유 - LIFO(Last In First Out) : 스택은 마지막에 삽입된 요소를 가장 먼저 꺼내는 자료구조다. dfs에서는 가장 최근에 발견된 노드를 먼저 탐색해야 하기 때문에, 노드를 탐색하면서 경로를 쌓아두었다가 더이상 갈 곳이 없을 때 되돌아가는데 적합하다.   dfs에서 A 에서 출발해서 E를 찾는 과정을 살펴보자. A에서 출발하여 B로..