코딩21 Knapsack알고리즘 Knapsack알고리즘 아래와 같이 n개의 물건과 각 물건i의 무게Wi와 가치Vi가 주어지고 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대가치를 찾는 문제를 다뤄본다. 단, 배낭에 담은 물건의 무게 합은 배낭의용량W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다. 배낭 문제를 DP로 접근해보자. 변수는 물건, 물건의무게, 물건의가치, 배낭의 용량 총 4가지 이다. 이 중 물건과 물건의 무게는 부분문제를 정의하는데 반드시 필요하다. 왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는것과 안담는것을 현재 배낭에 들어있는물건의 가치의 합에 근거하여 결정해야 하기 때문이다. 또한 물건을 배낭에 담으려고 할 경우 배낭용량의 초과여부를 검사해야 한다. W : 배낭의 용량 (vi, w.. 2022. 4. 5. [Java] 백준16926_배열돌리기 1 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net [문제] [입력] 4 4 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [출력] 3 4 8 12 2 11 10 16 1 7 6 15 5 9 13 14 package day05.ws; import java.util.Scanner; public class BJ16926 { publ.. 2022. 4. 2. [Java] SWEA1210_Ladder1 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제] 점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다. 김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다. 사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자. 아래 의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 .. 2022. 3. 21. [Java] Stack Stack : 자료구조 중 하나, 먼저 집어넣은 데이터가 가장 나중에 나오는 선입후출의 구조(LIFO: Last In First Out) top : 맨 위에 위치한 인덱스 -> 가장 최근에 들어온 데이터이자 다음에 출력될 값 [활용사례] 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) 재귀함수 = 깊이우선탐색 (DFS,Depth-First Search) 구현 [구현] Stack stack = new Stack(); stack.push() : 스택에 값 삽입 stack.pop().. 2022. 3. 19. [Java] Queue Queue Queue : 자료구조중 하나, 먼저 집어넣은 데이터가 먼저 나오는 선입선출의 구조(FIFO: First In First Out) Front : 맨 앞에 위치한 인덱스 -> 다음에 출력될 값 Rear : 맨 뒤에 위치한 인덱스 -> 가장 최근에 입력된 값 [활용] 너비 우선 탐색(BFS, Breadth-First Search) 구현 캐시(Cache) 구현 우선순위가 같은 작업 예약 선입선출이 필요한 대기열 콜센터 고객 대기시간 프린터의 출력 처리 윈도 시스템의 메시지 처리기 프로세스 관리 [구현] 큐는 인터페이스이기 때문에 LinkedList 또는 ArrayDeque로 구현해주어야 한다. Queue queue = new LinkedList(); 또는 Queue queue = new ArrayD.. 2022. 3. 19. [Java] SWEA1225_암호생성기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제] 다음 주어진 조건에 따라 n개의 수를 처리하면 8자리의 암호를 생성할 수 있다. - 8개의 숫자를 입력 받는다. - 첫 번째 숫자를 1 감소한 뒤, 맨 뒤로 보낸다. 다음 첫 번째 수는 2 감소한 뒤 맨 뒤로, 그 다음 첫 번째 수는 3을 감소하고 맨 뒤로, 그 다음 수는 4, 그 다음 수는 5를 감소한다. 이와 같은 작업을 한 사이클이라 한다. - 숫자가 감소할 때 0보다 작아지는 경우 .. 2022. 3. 17. 이전 1 2 3 4 다음
