복습노트 복습노트

문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krPRODUCT 테이블에서 상품 카테고리 코드(PRODUCT_CODE 앞 2자리) 별 상품 개수를 출력하는 SQL문을 작성해주세요. 결과는 상품 카테고리 코드를 기준으로 오름차순 정렬해주세요. SELECT SUBSTR(PRODUCT_CODE, 1, 2) CATEGORY, COUNT(*) productsFROM PRODUCTGROUP BY SUBSTR(PRODUCT_CODE, 1, 2)ORDER BY CATEGORY PRODUCT_CODE의 앞 두 자리를 뽑아내기 위해 SUBSTR함수를 사용했다. GROUP BY..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n개의 집이 있으면 각각 돈이 있다. 서로 이웃하지 않는 선에서 돈을 훔칠 때 가장 최댓값을 구하라. 단순히 생각하면 dp[i] = Math.max(dp[i-1], dp[i-2] + money[i]) 라고 점화식을 세울 수 있다. 하지만 집이 원형으로 이뤄져 있다는 점에서 다르게 생각해 주어야 한다. 즉, 첫번째 집을 선택하면 맨 마지막 집을 선택할 수 없습니다. 반대로 첫번째 집을 선택하지 않고 두번째 집을 선택하면 마지막 집까지 선택할 수 있습니다. 이를 dp 식으로 표현하면 아래와 같다. class..

문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 예를 들어 동전이 3개 주어지고, 각각 1, 5, 12 이고, k = 15이면 정답은 3이다. 전형적인 배낭 문제이다. int []coin = new int[n+1]; int []dp = new int[k+1]; for(int i=..

문제 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 4 * 4 크기의 칸에서 1 ~ 16번까지의 물고기가 들어간다. 처음 상어는 [0][0]에서 물고기를 먹고 물고기는 이동한다. 물고기가 이동하면 상어는 방향에 따라 갈 수 있는 공간에서 물고기를 하나 먹을 수 있다. 이러한 반복을 상어가 물고기를 못먹을 때 까지 반복한다. 정리하면 다음과 같다. 1. 상어는 물고기를 먹을 수 있으면 먹는다. 2. 1번 물고기 부터 시작해서 16번 물고기 까지 이동을 한다. 만약 이동을 못하게 되면 45도 반..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작업 순서를 설정해 작업 시간을 최소로 하는 문제이다. 예를 들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 그림으로 표현하면 아래와 같다. 이것을 차례대로 처리하면 아래 그림과 같다. 이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 된다. 하지만 A → C → B 순서대로 처리하면 이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료..

문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net n개의 서로 다른 금액의 동전이 주어지면 동전을 조합해서 m의 금액이 나올 수 있는 경우의 수를 구하는 문제이다. 예를 들어 n은 3이고 서로다른 동전은 2, 3, 5라고 할 때 m = 10이면 정답은 4가 된다. {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5} 여러 규칙을 찾으려 노력했지만 이러한 문제 유형은 배낭 문제이다. 위에 예시를 기반으로 표를 만들면 다음과 같다. 이를 코드로 구현하면 아래와..

문제 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 왼쪽 그림과 같이 n개의 노드가 주어지면 트리를 형성할 수 있다. 트리는 연속된 숫자여야 한다. 연속된 숫자는 하나의 집합이다. 연속된 숫자가 아니면 다음 집합으로 넘어간다. 이 때 K가 주어지는데 K의 사촌 수를 구하는 문제이다. 사촌 이란 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다. n개의 수는 오름차순으로 주어진다. 왼쪽의 예시는 1, 3, 4, 5, 8, 9, 15, 30, 3..

문제 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 명령어는 I 또는 Q가 주어진다. I가 주어질 경우 노드 2개가 추가로 주어진다. 예를 들어 I 1 2 라면 1번 노드와 2번 노드를 연결한다는 것이다. Q가 주어질 경우 노드 1개가 추가로 주어진다. 예를 들어 Q 1이라면 1번 노드가 포함된 그래프의 노드 개수를 구해주면 된다. 즉 1번과 2번이 연결되있으므로 정답은 2가 된다. 노드를 서로 합치는 것이기 때문에 union-find 알고리즘을 사용하였다. 연결하는 것은 쉬운데 어떻게 같은 집합의 노드 개수를 ..