프로그래밍 공방

문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제해결방법 이 문제를 해결하기 위해 DP[N+1][K+1] 배열을 사용했다. 먼저 n번째 꺼낸 물건의 무게와 가치를 w, v 이라고 했을 때, DP[n][k] 를 아래와 같이 채워주었다. k가 w보다 작은 경우에는 DP[n-1][k] (꺼낸 물건과 관계없이 현재까지의 최대 가치가 변하지 않는다.), k가 w이상인 경우에는 DP[n-1][k..

문제 programmers.co.kr/learn/courses/30/lessons/17680 코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 문제해결방법 1. 도시 이름을 키, 들어온 시간을 값으로 하는 Map을 생성한다. 2. 도시 ..

문제 programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제해결방법 1. check 함수를 통해 보드를 돌면서 지워지는 블록들을 체크한다. 2. redraw 함수로 블록들을 지우고 아래로 내린다. 3. 위 과정을 더 이상 블록이 지워지지 않을때까지 계산한다 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445..

문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 문제해결방법 1. 처음에 land 배열을 돌면서 사다리 없이 이동할 수 있는 격자들끼리 그룹을 지어주었다. 2. Union-Find 작업을 해주기 위해 그룹의 개수만큼 Parent 배열을 만들어주었다. 3. 다시 land 배열을 돌면서 각 격자마다 상,하,좌,우를 확인하며 그룹이 다르면 사다리를 놓을..

문제 leetcode.com/problems/median-of-two-sorted-arrays/ Median of Two Sorted Arrays - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제해결방법 이 문제는 정렬된 두 배열이 주어지고 두 배열을 합쳤을때 중앙값을 구하는 문제였다. 각 배열에 시작 인덱스를 두고 각 배열의 원소들을 앞에서부터 비교해가면서 두 배열을 합친 길이의 중간 개수까지 세준다. 코드 12345678910111213141516171..

문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제해결방법 이 문제는 DP 배열에 왼쪽부터 N번까지 마시며 최대로 마실 수 있는 값을 기록해가면서 풀었다. N번 포도주를 마실때 계산해줘야 하는 경우는 아래와 같다. 1. N번 포도주를 안 마시는 경우 -> DP[i-1] 2. N번 포도주를 마시는 경우 - DP[N-2] + N번 포도주의 양 (N-1번을 건너뛰고 마시는 경우) - DP[N-3] + N-1번 포도주의 양 + N번 포도주의 양 (N-2번을 건..

문제 programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 문제해결방법 1. 입력받은 2개의 문자열에 있는 모든 소문자를 대문자로 바꿔주었다. 2. 각 문자열을 돌면서 글자 쌍을 Key로, 글자 쌍이 나오는 수를 Value로 각각의 Map에 넣어주었다. 3. 두 Map의 Key를 비교해가면서 양쪽에 다 있는 Key만 더 작은 Value를 교집합으로 카운트했다. 4. 2번 과정에서 합집합의 크기를 구하고, 3..

문제 programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 문제해결방법 이 문제는 단순하게 각 지도의 정수 배열을 비교해가며 전체 지도를 만들어주었다. 코드 12345678910111213141516171819202122232425262728293031package Programmers; public class Solution_보물지도 { public static String makeMap(int n, int a, int..

문제 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제해결방법 이 문제를 풀기 위해 시작 인덱스와 끝 인덱스 두 개의 포인터를 사용하였다. 1. gems를 돌면서 Map에 존재하면 pass, 존재하지 않으면 해당 보석 이름을 Key로, Value를 0으로 해서 맵에 넣어준다 -> 맵에 넣어줄때마다 카운트해서 보석의 종류의 개수를 알 수 있다. 2. 끝 인덱스를 배열의 0에서부터 증가시켜가며 보석의 종류별로 나온 횟수를 센다. (0에서 1이 되는 경우 카운트 하여 보석 ..

문제 www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제해결방법 이 문제를 해결하기 위해, 0인 곳을 1로 만들어서 상, 하, 좌, 우에 있는 모양들이 연결되도록 하고, 그 결과로 만들어지는 가장 큰 모양을 찾아야 겠다고 생각했다. 1. 처음에 배열을 돌면서 BFS를 통해 연결 요소들을 찾아 각 연결 요소에 번호를 붙이고 Map에 그 번호를 Key로 사이즈를 Value로 해서 저장해줬다. 2. 다시 한 번 배열을 돌면서 0인 곳마다 상, 하, 좌..