목차1. 문제 설명2. 정답 1. 문제 설명https://www.acmicpc.net/problem/12865 정말 말그대로 평범한 배낭 알고리즘 문제로, 점화식을 도출하는 방법을 정리해보려고 한다.배낭 알고리즘은 전형적인 dp문제다. 결국에 배낭에 물건을 담냐, 담지 않느냐로 쪼갤 수 있기 때문이다. 먼저 dp 배열을 정의해보자. dp[i][w]i번째까지의 물건을 고려했을 때무게 w를 버틸 수 있는 배낭의 최대 가치 물건을 선택할 때에는 두 가지 선택지가 있다. 1. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게를 초과 첫 번째 물건의 무게는 8kg로 배낭에 최대로 담을 수 있는 무게인 7kg를 초과한다.이 경우, 배낭에 물건을 담을 수 없다.따라서 이전 상태의 값을 그대로 가져..
목차1. 문제 설명2. 정답 1. 문제 설명https://www.acmicpc.net/problem/2146 지도가 주어질 때 가장 짧은 다리를 하나 놓아 두 대륙을 연결하는 방법을 찾는 문제다. 바다 = 0육지 = 1위의 그림과 같이 지도가 주어지면 회색 영역의 섬을 dfs로 구한다.바다와 육지가 각각 0, 1의 값을 사용하기 때문에 각각의 섬에 2부터 번호를 부여한다. 즉 dfs로 모든 영역을 순회했을 때 각각의 섬은 오른쪽 사진과 같은 번호를 부여받는다. 두 대륙을 연결하는 가장 짧은 다리는 (해안선과 근접한 육지) - (해안선과 근접한 육지)간의 최단 거리와 같다. Q. 최단 거리를 구해야한다면?A. bfs를 써야 한다는 뜻이다! 그렇다 이 문제는 dfs + bfs 짬뽕인 것이다....
목차1. 문제 설명2. 정답 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/301651 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 위 문제의 핵심은 먼저 각 세대별 대장균을 구하고, 세대 별 자식이 없는 개체 수와 세대를 출력하는 것이다.테이블엔 몇 번째 세대까지 존재하는지 알 수 없고, 정확히 몇 번째 세대에 대한 결과를 구하는 문제가 아니기 때문에 재귀를 사용해야 함을 알 수 있다. SQL에서도 재귀가 가능한가?당연히 가능하다. CTE 문법과 RECURSIVE를 활용하면 된다.MySQL과 Oracle 모두 CTE 문..
목차1. 문제 설명2. 정답 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/299305 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제의 핵심은 자식이 없는 대장균 또한 출력에 포함시켜야 한다는 것이다. 1. ECOLI_DATA 테이블을 하나는 자식, 하나는 부모라는 이름을 붙여 조인2. 그룹화3. 집계 함수 써서 출력 과정을 떠올리긴 했는데 집계 함수 어떻게 써야 될지 뇌정지 와서... 쓸데없이 어렵게 풀었다.자식이 있는 테이블과 자식이 없는 테이블에서 각자 ID와 자식 개수를 구하고 그 결과를 UNION 하여 결과..
목차1. 문제 설명2. 정답 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/301646 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해당 문제의 핵심 조건은 2번 형질을 보유하지 않으면서 1번이나 3번 형질을 보유해야 한다는 것이다. 먼저 형질은 비트마스크 방식으로 저장됨을 알아야 한다.비트마스크 방식 각 형질을 하나의 비트로 표현하는 방식이다.1번 형질 = 0001₂ (1)2번 형질 = 0010₂ (2)3번 형질 = 0100₂ (4)4번 형질 = 1000₂ (8)즉 각 형질은 해당하는 비트 자리(2의 거듭제곱)로..
