📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/181188 📍알고리즘 분류 - 그리디 📍문제 풀이 [시작 좌표, 종료 좌표] 가 배열로 주어진다 const targets = [ [4, 5], [4, 8], [10, 14], [11, 13], [5, 12], [3, 7], [1, 4], ]; 이 좌표들을 선으로 그었을 때, 모든 수평선을 수직으로 가로지르는데 필요한 최소한의 수직선의 갯수를 구하면 된다. 그림으로 나타내면, 아래처럼 표현할 수 있는데, 겹치지 않는 수평선이 총 3개 이므로, 최소 3개의 수직선이 필요하다. 겹치지 않는 수평선인지 아닌지를 빠르게 파악하려면, 모든 좌표들을 종료지점을 기준으로 오름차순 정렬한 후, 순서대로 ..

📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150370 📍알고리즘 분류 - 구현 📍문제 풀이 - 약관 A, B, C 에 따라 각각 유효 개월 수가 자연수로 주어진다 - 최초 개인정보 수집 일자가 2021.05.02 처럼 문자열로 주어지고, 어떤 약관 종류인지 주어진다 - 오늘 날짜가 2021.05.02 처럼 문자열로 주어진다 이 때, 각 개인정보 수집 일자에 대해서, 약관의 개월 수에 따라 오늘 시점에서 파기해야 할 수집 일자 번호를 반환한다 1. 최초 개인정보 수집일자에다 유효 개월 수를 더해 최대 보유 가능 일자를 구한다 2. 최대 보유 가능 일자가 오늘 날짜보다 작으면 파기해야 하므로 결과에 추가한다 주의할 점 오늘은 2022..

📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/172928 📍알고리즘 분류 - 구현 📍문제 풀이 N * M 크기의 2차원 배열 park가 주어진다. 이차원 배열은 하나의 S, 여러개의 O, X로 구성되어 있다 - S : 시작 좌표 - O : 이동 가능한 좌표 - X : 장애물 (이동 불가) 좌표 그리고 "E 2", "N 1" 처럼, 동서남북 방향과 이동거리가 원소인 배열 routes가 주어진다 routes 를 순회하며, route의 이동 결과가 N * M을 넘지 않고, 장애물을 만나지않을 경우에만 좌표를 움직인다 그리고 최종 결과를 출력한다 📍코드 (JavaScript) const park = ["OSO", "OOO", "OXO", "..

📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/131705 📍알고리즘 분류 - 백트래킹 📍문제 풀이 - 중복된 수가 있을 수 있는 정수 배열이 주어진다. 정수 배열에서 3개의 숫자를 뽑아서 (조합) 합이 0이 되는 경우의 수를 구하라 백트래킹을 이용해서 조합을 구현할 수 있다 📍코드 (JavaScript) function solution(number) { const chosenNums = []; // 뽑힌 숫자들 (조합) const isUsed = []; // 중복을 막기 위해 사용됐는지 확인할 배열 let answer = 0; // 가짓수 // 백트래킹 function recursive(depth, start) { if (depth ..

📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/178871 📍알고리즘 분류 - 구현 📍문제 풀이 - 달리기 경주중인 상황에서, 현재 선수들의 이름이 순위 순서로 배열로 주어진다 -> string[] - 어떤 선수가 1번 추월에 성공하면, 그 선수의 이름을 추월한 순으로 배열로 저장한다 -> string[] 추월 기록 배열을 순회하며 현재 순위별 선수 이름 배열을 업데이트하고 출력하라 단순하게 swap 함수를 만들어서 배열을 직접 조절했는데, 시간 초과가 발생했다. 시간 복잡도가 O(N^2)가 되는데다, 배열에서 원소를 움직이는 작업은 계산 비용이 크기 때문인 듯 하다 어떻게 할까.. 고민하다가 하나의 객체만 활용해서 시간을 줄이려고 해..

📍문제 링크 https://www.acmicpc.net/problem/18230 18230번: 2xN 예쁜 타일링 첫째 줄에 정수 N, A, B(1 ≤ N, A, B ≤ 2000, 2 × B + A ≥ N)가 공백으로 구분되어 주어진다. 둘째 줄에 각 2×1 크기 타일의 예쁨을 의미하는 정수 A개가 공백으로 구분되어 주어진다. 셋째 줄에 각 2× www.acmicpc.net 📍알고리즘 분류 - 그리디 알고리즘 - 정렬 📍문제 풀이 2 * 1 타일과 2 * 2 타일에 점수가 있을 때, 정해진 공간 N에 타일을 깔며 점수 최대값을 획득하는 문제 각 타일 배열을 오름차순으로 정렬하여 pop으로 꺼내서 사용 (성능을 위해) 2 * 1 타일 2개의 점수와 2 * 2 타일 1개의 점수를 비교하여 큰 쪽을 사용 N ..

📍문제 링크 https://www.acmicpc.net/problem/18233 18233번: 러버덕을 사랑하는 모임 첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000) 그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 xi와 yi가 공백으로 구분되어 주어진다. (1 ≤ xi www.acmicpc.net 📍알고리즘 분류 - 브루트포스 📍문제 풀이 (백트래킹) DFS를 활용해 nCp 조합을 구하고, 각 경우의 수가 범위를 만족하면서 전체 합이 E인 것을 구하면 된다 1. 조합을 구해야 하므로 백트래킹 코드를 만든다. 스택에는 실제 데이터가 아닌 인덱스만 담는 것이 간편하다 (중복을 제거하기 쉽고, 속도도 빠름) 2. p 가짓수..

📍문제 링크 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 N * N (4 { const N = +input.shift(); const board = input.map((row) => row.split(" ").map(Number)); // 아예 memo를 여유있게 넉넉하게 만들기 const memo = Array.from({ length: N + 10 }, (_) => Array..