두 번째 뇌

개요 백준 1167번 문제입니다. 문제는 풀었는데... 접근하는 방법(공식)을 모르고 있었던 상태였습니다. 그림으로 그려보면서 어떤 규칙이 있는지 찾아보았습니다. 그 결과, 속도가 매우 느리더군요ㅠ 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 접근법 저 같이 그림을 그려서 할 정도로 이해가 안되시거나, 접근법이 떠오르지 않으시는 분들은 '트리의 지름'이라고 구글링 해보세요. 이러한 문제에서 나타나는 규칙을 공식화 해둔 ..

개요 백준 1010번 문제입니다. 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 접근법 주어진 그림이 어려울 수 있는데, 직접 점과 선으로 연결해보면 이 형태가 파스칼 삼각형을 이루는 것을 알 수 있습니다. 그에 맞춰 구현합니다. 코드 🤩 : DP /** * 입력 */ // const fs = require('fs'); // const os = require('os'); // const input = fs.readFileSync('dev..

ERROR in ./index.js Module build failed: Error: Plugin/Preset files are not allowed to export objects, only functions. webpack build 시 나는 에러인데... 자꾸 빌드에 실패해서 찾아봤습니다. babel 6 -> 7로 업그레이드 되면서 생긴 의존성 문제로, webpack.config.js를 직접 만들어 사용하시는 분들이 특히 발생하는 것 같습니다. 아래를 확인해주세요! npm install --save-dev @babel/preset-react npm install --save-dev @babel/preset-env 또한 webpack.config.js 파일의 preset을 수정해주셔야 합니다. { "..

개요 백준 1003번 피보나치 함수 문제입니다. top-down 형식의 재귀풀이가 아닌 bottom-up 형식의 DP를 사용하여 풀었습니다. 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근법 코드 🤩 : DP # 메모이제이션 N = int(input()) result = [] for _ in range(N): T = int(input()) dp = [[1, 0], [0, 1], [1, 1], [1, 2]] + [[0, 0] for _ in range(T-3)] for i in range(4, T+1): dp[i][0] = dp[i..

1003번 문제 피보나치 함수 접근법 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치 수에 적용되는 규칙은? 메모이제이션(Memoization)을 활용해봅니다. 9184번 문제 신나는 함수 실행 접근법 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1003번의 응용입니다. 1904번 문제 01타일 접근법 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물..

11654번 문제 아스키 코드 접근법 11654번: 아스키 코드 알파벳 소문자, 대문자, 숫자 0-9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오. www.acmicpc.net ord() 함수를 사용하면 해당 문자의 아스키코드를 가져올 수 있고, chr() 함수를 사용하면 해당 아스키코드를 문자로 변경할 수 있습니다. 11720번 문제 숫자의 합 접근법 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 문자열은 배열 기능을 지원하므로 loop를 돌면서 원소를 int()로 정수형 치환 후 누적합을 반환합니다. 10809번 문제 알파벳 찾기 접근법 10809번..

개요 상반기 카카오 인턴십 문제로 출제되었던 Level 2 코딩테스트 문제입니다. DFS를 충분히 활용해서 풀어야겠지만... 아직 이론을 이해하지 못해서ㅠ 코드가 길어진 것 같습니다. 문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP..

개요 주어지는 배열에서 특정 값을 찾아내는 알고리즘을 작성할 때, 일반적으로 loop문을 두 번 중첩해서 사용합니다. 물론 주어지는 배열의 크기가 10,000 이하인 경우 최대 O(n^2) 내에서 해결하면 되므로 문제가 없으나.... 그 이상이 주어진다면 그 속도는 기하급수적으로 차이가 납니다. 투 포인터 알고리즘은 포인터 두개를 둬서, 시간복잡도를 O(n) 내로 해결하는 방식입니다. 문제 주어지는 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하라. 만약 M=6이고 수 열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지이다. ▣ 입력설명 첫째 줄에 M(..