Problem Solving

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/388354 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제에는 각 노드에 대한 정의가 나와있다.모든 노드는 홀수 노드, 짝수 노드, 역홀수 노드, 역짝수 노드 중 하나이며 홀짝 트리와 역홀짝 트리는 아래의 노드로만 이루어진 트리를 의미한다. 홀짝 트리역홀짝 트리홀수 노드역홀수 노드짝수 노드역짝수 노드 2. 접근 방식문제에서 주어진 트리는 루트 노드가 설정되어 있지 않다. 루트 노드와 루트 노드가 아닌 일반 노드는 어떤 차이점이 있을까?..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있고, 벽이 있는 칸에는 경주로를 건설할 수 없다. 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로라고 한다. (개당 100원)두 직선 도로가 서로 직각으로 만나는 지점을 코너라고 부른다. (개당 500원) 경주로를 건설하는데 필요한 최소 비용을 구하는 문제이다. 이때 언제 코너가 만들어지는지 계산하려면 ..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://www.acmicpc.net/problem/5052 전화번호 목록이 주어질 때, 목록에 일관성이 있는가를 검사하는 문제이다.일관성은 한 번호가 다른 번호의 접두어가 되는가를 기준으로 평가한다. 한 번호가 다른 번호의 접두어가 된다. → 일관성 X긴급전화 : 911선영 : 91 12 54 26한 번호가 다른 번호의 접두어가 아니다. → 일관성 O긴급전화 : 911수연 : 91 22 54 26 2. 접근 방식일관성이 없는 경우는 접두어가 같다는 조건을 활용하기 위해 정렬 을 떠올렸다. 입력값이 다음과 같이 주어졌을 때 91191091129129113 전화번호 목록을 String을 기준으로 정렬하면 아래와 같은 순서가 된다. ..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr "ICN"에서 출발해 방문하는 모든 공항 경로를 출력하는 문제이다. 이때 공항 수는 3개 이상 10,000개 이하이다. 출발지도착지ICNSFOICNATL 예제 2처럼 가능한 경로가 2개 이상인 경우엔 알파벳 순서가 앞서는 경로를 먼저 방문한다.가능한 경로가 2개 이상이면 오름차순 정렬된 결과를 선택해야 한다는 의미로위의 표를 기준으로 ATL을 먼저 방문해야 한다. 2. 접근 방식방문..

목차1. 문제 설명2. 접근 방식3. 코드 1. 문제 설명https://www.acmicpc.net/problem/1197 최소 스패닝 트리의 가중치를 구하는 문제이다. 최소 스패닝 트리는 그래프의 모든 정점들을 연결해야 하기 때문에 간선의 수는 노드 - 1개를 가진다. 또한 가중치의 합이 최소로 만들기 위해 사이클을 가지면 안 된다.1 - 2 / 1 - 3이 연결되어 있을 때 이미 모든 정점을 움직일 수 있기 때문에 2 - 3을 포함하면 가중치에 불필요한 값이 추가되며, 사이클이 발생한다. 2. 접근 방식가중치의 합을 최소로 만들어야 한다 = 가중치가 작은값부터 쏙쏙 골라간다 1. 먼저 모든 간선들을 가중치를 기준으로 오름차순 정렬2. 해당 간선을 포함했을 때 사이클이 안생긴다 → 최소..

목차1. 문제 설명2. 접근 방식3. 코드4. 시간 복잡도 및 공간 복잡도 계산 1. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 핵심 조건은 아래와 같다. 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대 추가n * m → 최소 n대의 증설된 서버가 필요k = 5 ) 10시에 증설한 서버는 10 ~ 15시에만 운영 0 ~ 23시까지의 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 구하면 된다. 2. 접근 방식players의 길이, m,..

목차1. 문제 설명2. 접근 방식3. 코드4. 시간 복잡도 및 공간 복잡도 계산 1. 문제 설명https://www.acmicpc.net/problem/1138 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. 입력값으로 키가 1인 사람부터 차례대로 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 주어지면, 실제로 줄을 선 순서대로 키를 출력해주면 된다. 2. 접근 방식예제 입력 1을 기준으로 아래와 같이 해석할 수 있다. 키 1 : 왼쪽에 자기보다 키 큰 사람 2명키 2 : 왼쪽에 자기보다 키 큰 사람 1명키 3 : 왼쪽에 자기보다 키 큰 사람 1명키 4 : 왼쪽에 자기보다 키 큰 사람 0명 int[] arr에 [ 2, 1, 1, 0 ] 을 저장한다고 가정할 때 ✅️ 만약..

목차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 문..