본문 바로가기

728x90
반응형

Major-

(865)
[Ch.10 - DP] 01. 계단오르기 1. 계단오르기 설명 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 입력 첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다. 출력 첫 번째 줄에 올라가는 방법의 수를 출력합니다. 예시 입력 1 7 예시 출력 1 21 복잡한 문제의 경우 직관적으로 알 수 있는 단위인, 작은 문제들로 쪼갠 후, 확장을 하는 방식으로, 메모이제이션을 이용해 해결 -> DP (Dynamic Programming) dy[7]=? dy[1]=1 dy[2]=2 dy[3]은 dy[1]에서 혹은 dy[2]에서 ..
[프로그래머스 - 시뮬레이션] 04. 숫자 게임 4. 숫자 게임 문제 설명 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다. 전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 ..
[프로그래머스 - 이분탐색] 03. 예산 ## (+ 유효한 lt, rt 정하기) 3. 예산 문제 설명 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대..
[프로그래머스 - 정렬] 02. 가장 큰 수 2. 가장 큰 수 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예numbersreturn ..
[프로그래머스 - 그리디] 01. 기지국 설치 1. 기지국 설치 문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.) 초기에, ..
[Ch.07 - BFS] 01. 이진트리 순회 (+ 넓이우선탐색 BFS) 1. 이진트리 순회 (넓이우선탐색 : 레벨탐색) Breadth First Search (BFS : 낮은 레벨부터 탐색) -> 현재 위치에서의 최단 거리 탐색에 사용 //큐에 넣어서, 낮은 레벨부터 출력 Queue Q = new LinkedList(); Q.offer(root); int L=0; while(!Q.isEmpty()) { //비어있으면 거짓, 비어있지 않으면 참 -> 비어있을 때까지 반복 ~ } L++; 큐의 원소 개수를 위한 변수 설정 현재 노드 출력 연결된 자식들 넣기 현재 노드의 왼쪽 노드가 존재한다면, 왼쪽 노드 삽입 현재 노드의 오른쪽 노드가 존재한다면, 오른쪽 노드 삽입 큐 그리기 : 1 넣기 -> 1과 연결된 2,3 넣기 -> 2와 연결된 4,5 넣기 -> 3과 연결된 6,7 ->..
[Ch.07 - DFS] 02. 부분집합 구하기 2. 부분집합 구하기 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요. 입력설명 첫 번째 줄에 자연수 N(1 부분집합 해당 오른쪽 자식 -> 부분집합이 아님 DFS(1)을 넣어서 시작 -> 1부터 시작, ++해서 1이 n+1이 될때까지 package dfsbfs.ch07; import java.util.Scanner; //부분집합 구하기 (DFS) //주어진 N을 이용해 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 //공집합 출력하지 않는다. //2n^-1 [공집합 제외] public class Dfsbfs02 { // D(1) -> O / X로 부분집합이 될 때도, 안 될 때도 존재하므로, 이진트리 이용 // D(1) -..
[Ch.07 - DFS] 01. 이진트리 순회 (+ 깊이우선탐색 DFS) 1. 이진트리 순회 (깊이우선탐색) /_ 전위 순회 : 1234567 ∧ 중위 순회 : 4251637 _\ 후위 순회 : 4526731 Depth First Search (DFS : 깊이우선탐색) -> 가장 낮은 깊이 부터 우선 탐색한다. 구현 노드 클래스 -> 생성자 정의 트리 만들기 -> root -> 데이터 삽입 트리 객체를 인스턴스변수로 만들어서 메서드 생성 후, 호출하는 방식 package dfsbfs.ch07; //DFS -> 백트래킹 //Depth frist search; 깊이 우선 탐색 //이진트리 -> 부모노드, 왼쪽자식노드, 오른쪽자식노드 //루트 노드 -> 왼쪽 노드 -> 왼쪽 노드 [마지막 노드면] -> 오른쪽 노드 [마지막 노드면] -> 오른쪽 노드 //왼쪽 노드 -> 왼쪽 노드 ..

728x90
반응형