문제 링크 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 은행 인출(mid) 하고 cnt = 1 한 초기 상태에서 일별 사용금액을 차감하면서 부족할 경우 추가 은행 인출(cnt += 1) - (100, 400), (300,100), (500), (101), (400) 형태가 최대값 만약 N일이 10만이고, 각 금액이 1만이면 최대 10^9이 되야 1번(M)번에 처리가 가능 =..

문제 링크 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 - 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 - 시간 복잡도는 O(NlogN) 범위 지정시 (L, R) L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분) 최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 L 은 고로 주어진 배열에서 가..

문제 링크https://www.acmicpc.net/problem/1300 1300번: K번째 수세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 Bwww.acmicpc.net2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :) 풀이 - N (최대 10만), K (10만 ~ 10억)- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 - N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능 아래와 같은 연산..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이진탐색 (매개변수 탐색) 풀이하면 되는 문제 문제 지문 K개 랜선이 있을때 필요한 랜선 N개를 만들기 위한 최대 랜선 길이 H를 구하시오. 뒤집은 지문 (매개변수 탐색*) 임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가? 시간 복잡도 O(NlogN) 최대값 랜선의 길이 최대값이 2^31 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 매개변수 (paramatrix search) 탐색 문제 (그리디 포함) 문제 지문 C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오. 뒤집은 지문 두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dm..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 반복문을 통해 left = 1 ~ N 까지 조회할 때 - arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함 - N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능 - 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐 투 포인터로 풀 경우 좀 더 쉽게 풀이 가능 주..

문제 링크 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 - 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 - 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택) - 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2

Primitive type - 총 8가지의 기본형 타입을 자바에서 제공함 - 기본값을 제공하기 때문에 Null이 존재하지 않음. 만약 기본형 타입에 Null을 넣고 싶은 경우 Wrapper class를 활용해야함 - 실제 값을 저장하는데, 이때 Stack(스택) 메모리에 저장됨 타입 할당 메모리 크기 데이터 표현 범위 논리형 boolean 1byte false, true 정수형 byte 8bit (1byte) -128 ~ 127 short 16bit (2byte) -32,768 ~ 32,767 int 32bit (4byte) -2,147,483,648 ~ 2,147,483,647 long 64bit (8byte) -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 - 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름) - '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음 점화식 - 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함 - 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] - 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 - bottom-up 방식으로 품 // SUCCESS const input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const n = Number(input[0]); const dp = new Array(n+1).fill(0); for(let i = 2; i

동적 프로그래밍 (DP, Dynamic Programming) - 통산적으로 메모리를 더 사용하여 시간 복잡도 개선할 때 많이 사용됨 - DP로 문제를 해결하기 위해 '점화식'을 찾는 것이 핵심 과정 동적 프로그래밍은 아래의 두 조건을 만족할 때 사용가능하다 1. 최적 부분 구조(optimal substructure) 큰 문제를 유사한 형태의 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다. 2. 반복되는 부분 문제(overlapping sub-problem) 동일한 작은 문제를 반복적으로 해결해야 한다. 점화식 - 인접한 항으로 현재 값을 결정하는 관계식을 의미함 - 점화식은 "재귀 함수"로 표현가능 예) 파보나치 수열 점화식 An = (An-1) + (An-2) (이때 초기값..

후기🧑‍💻 약 2년 전 단기간 코딩 테스트 준비를 하여 더 나은 곳으로 이직을 할 수 있었다. 실무에서 코딩 테스트와 같은 문제를 요구하지는 않지만, 문제 해결 과정에서 필요한 자료 구조 유형을 판단하여 사용하거나 알고리즘 기법을 응용해서 적용하거나 할 수 있었다. 이는 이전에는 할 수 없었던 경험이었다. 그러나 시간이 지남에 따라 잊게 되고, 할 줄 아는 거만 반복하는 모습에서 기본기가 부족한 게 아닌가 싶은 고민을 하고 있었고, 이러한 상황에서 기회가 되어 강의를 수강할 수 있었다. 한 단계 더 성장 강의 해설에 절차 지향적인 코드와 설명을 접하더라도 이해가 되지 않는 경우가 많았다. 그럴 때 마다 시야를 넓혀서 기술 블로그/유튜브 등을 통해 앞서 고민했던 사람의 흔적을 볼 수 있었고, 그 결과 새로..

온라인 코드 테스트 사이트 https://replit.com/ https://www.jdoodle.com/execute-nodejs-online/ Ch 10. 최단 거리 다익스트라 알고리즘(Dijkstra Algorithm) - 시작 노드를 기준으로 다른 모든 노드로 가는 최단 경로를 계산 - 간선의 가중치가 양수(>= 0)인 경우에 최단 거리를 구할 수 있음 - 다익스트라 알고리즘은 그리디(탐욕) 알고리즘으로 분류됨 => 매 상황에서 가장 비용이 작은 노드를 선택해 알고리즘 과정을 반복함 - 시간 복잡도 : O(ElogV) 다익스트라 알고리즘의 기본적인 구조/절차는 아래와 같다 * 알고리즘 동작과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 (이때, 출발 노드는 0, 그 외는 INF) 3. 방..

온라인 코드 테스트 사이트 https://replit.com/ https://www.jdoodle.com/execute-nodejs-online/ Ch 07. DFS (깊이 우선 탐색) 알고리즘 문제 1-1) 바이러스 (실버3) - 양방향 그래프로 생각하고 인접 리스트 표현하기 // SUCCESS const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().split('\n'); const n = Number(input[0]); const v = Number(input[1]); const matrix = []; for(let i = 0; i = row || y >= col) return false; if(matrix[x]..

온라인 코드 테스트 사이트 https://replit.com/ https://www.jdoodle.com/execute-nodejs-online/ ch04. 그리디(탐욕) 알고리즘 추후 예정 문제 목록 더보기 문제 1-1) 동전0 문제 1-2) ATM 문제 1-3) 잃어버린 괄호 문제 2-1) 설탕배달(실버4) 문제 2-2) A -> B(실버2) 문제 2-3) 수들의 합 문제 2-4) 신입사원 문제 3-1) 주유소 문제 3-2) 회의실 배정 문제 3-3) 풍선 맞추기(골드5) 문제 3-4) 피보나치(실버1) 문제 4-1) 박 터뜨리기(실버4) 문제 4-2) 회문(골드5) 문제 4-3) 박스 채우기(골드3) ch05. 이진 탐색 순차탐색 이진탐색 - 리스트 안에 특정 데이터 찾기 위해 앞에서 부터 순차적으..

온라인 코드 테스트 사이트 https://replit.com/ https://www.jdoodle.com/execute-nodejs-online/ 빅오 표기법(Big-O Notation) 시간 복잡도 의미 O(1) 상수 시간(constant time) O(logN) 로그 시간(log time) O(N) 선형 시간(linear time) O(NlogN) 로그 선형 시간(log-linear time) O(N^2) 이차 시간(quadratic time) O(N^3) 삼차 시간(cubic time) O(2^N) 지수 시간(exponential time) - 시간 복잡도 (time complexity) : 알고리즘에 사용되는 연산 횟수 측정 - 공간 복잡도 (space complexity) : 알고리즘에 사용되는..

Convention 정하지 않고 작업하게 될 경우, 서로 다른 작성 방식으로 인해 코드 가독성 저하를 일으키고 장기적으로 볼 때 유지 보수 함에 있어 큰 문제를 야기할 수 있습니다. Team Convention - 코드 스타일을 통일 시키는데 있어 Prettier 미사용하기로 함 - 규칙이 상대적으로 적고, 인텔리제이에서 제공하는 기능을 활용하는게 더 나은 것으로 판단했기 때문 설정 파일 .editorconfig 인텔리제이 설정 [File > Settings> Editor > Code Style] 이동 General Tab 에서 Enable EditorConfig Support 옵션 ✔ (=.editorconfig 설정 파일 허용) Formatter Tab에서 Do not format 에 제외 대상 gl..

Convention 정하지 않고 작업하게 될 경우, 서로 다른 작성 방식으로 인해 코드 가독성 저하를 일으키고 장기적으로 볼 때 유지 보수 함에 있어 큰 문제를 야기할 수 있습니다. Team Convention JS 코드 형식이 사람마다 미묘하게 차이나서, 통일 시켜 일관성을 맞추고 신경쓰지 않고 자동화될 수 있도록 사용하게 됨 ESLint 활용하여 JavaScript Code Convention 검사 수행 (ES6 기준) husky , lint-staged 활용하여 pre-commit 단계에서 staged file 대상으로 ESLint 검사 자동화 Automatic ESLint 아래의 플러그인 활용하여 자동화 수행 husky : Git hook 편리하게 사용할 수 있도록 지원 ( pre-commit 활..