코딩 테스트 정복기

[level 3] 코딩 테스트 공부 - 118668문제 링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이DP를 이용해 해당 문제를 해결할 수 있다.먼저 가능한 선택지는 3가지 이다. 1시간을 사용, `alp` 1 늘리기1시간을 사용, `cop` 1 늘리기문제를 해결하여 주어진 `cost`를 사용, `alp_rwd`, `cop_rwd` 만큼 늘리기row를 `alp`, col을 `cop`으로 두고 `[alp][cop]`에 시간(`cost`)을 저장하여 DP를 수행한다.각 [알고력, 코딩력]에 도달하기 위한 경우의 수 중 cost가 가장 적은 것을 선택한다.현재 `[alp][cop]`에서 1시간을 ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr[level 3] 파괴되지 않은 건물 - 92344 풀이해당 문제는 누적합으로 해결한다. (r1, c1)에서 (r2, c2)까지 n을 더할 때, 문제처럼 해당 과정이 k만큼 수행되어야 한다면for문으로 작업 시 r*c*k 만큼 수행해야한다. 이는 효율적이지 않다.때문에, 주어진 r1, c1, r2, c2를 이용하여 더하는 구간을 표시하고 이를 더하는 누적합을 수행한다. 아래 이차원 배열에서 (0, 0) 부터 (3,3) 까지 5를 더한다고 하자..

문제3열 N행의 가중치가 있는 배열 arr이 주어집니다.이 배열에 다음 규칙을 준수하면서 조약돌을 놓을 때 최대 가중치의 합을 반환하는 Solution() 함수를 구현하세요. 제약조건• 각 열에 조약돌은 적어도 하나는 놓아야 합니다.• 각 조약돌에 바로 인접한 위치에 조약돌을 놓을 수 없습니다.- 인접 기준은 상하좌우입니다. 입출력의 예arrreturn[ [ 1, 3, 3, 2 ], [ 2, 1, 4, 1 ], [ 1, 5, 2, 3 ] ]19[ [ 2, 7, 13, 2, 6 ], [ 2, -4, 2, 5, 4 ], [ 5, 3, 5, -3, 1 ] ]32   풀이 및 코드3열 N행에서 각 열에 조약돌을 놓는 방법은 다음과 같다.예) 1행에서1. 1열에 두는 방법이전 행에서 2열이나 3열을 선택했을 때 ..

[Gold V] 용액 - 2467문제 링크분류이분 탐색, 두 포인터문제 설명KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98..

문제정수배열 nums에서 LIS의 길이를 찾는 함수를 작성하세요.제약조건• nums는 최대길이 1,000의 정수 배열입니다.• nums의 각 요소는 -1,000 이상 1,000 이하의 정수입니다. 입출력 예numsreturn[1, 4, 2, 3, 1, 5, 7, 3]5[3, 2, 1]1   풀이 및 코드LIS(Longest Increasing Subsequence)란?"최장 증가 부분 수열"이라고도 하며, 주어진 수열에서 엄격히 증가하는 가장 긴 부분 수열을 찾는 문제이다.부분 수열은 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들만 선택한 수열을 의미한다. 예를 들어, `[1, 4, 2, 3, 1, 5, 7, 3]` 에서 LIS는 `[1, 2, 3, 5, 7]`이다. 동적 계획법 (Dynamic..

[Gold V] 다각형의 면적 - 2166문제 링크분류기하학, 다각형의 넓이문제 설명2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.출력첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.    풀이 및 코드다각형의 면적을 구하는 문제는 "신발끈 공식" 을 이용하여 풀 수 있다.신발끈 공식좌표평면상 점의 좌표를 이용하여 볼록 및 오목 다각형의 넓이를 계산하는 공식으로, n각형의 각 꼭짓점을 시계 반대..

[Gold V] 치킨 배달 - 15686문제 링크성능 요약메모리: 16092 KB, 시간: 104 ms분류백트래킹, 브루트포스 알고리즘, 구현 문제 설명크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리..

[Gold IV] 행렬 제곱 - 10830문제 링크성능 요약메모리: 18780 KB, 시간: 204 ms분류분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학, 수학제출 일자2024년 12월 19일 17:29:58문제 설명크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.입력첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.출력첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.     풀이..

[level 4] 지형 이동 - 62050문제 링크성능 요약메모리: 97.8 MB, 시간: 82.65 ms구분코딩테스트 연습 > Summer／Winter Coding（2019）채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 12월 18일 01:09:54문제 설명N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우..