두부의 코딩일기

https://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 문제이다. dp문제는 점화식만 찾으면 쉽게 해결할 수 있는 알고리즘으로 개인적인 팁을 주자면 필자는 dp 문제를 보면 공책에다가 표를 그려서 완전 탐색을 해본다. 물론 표를 그려본다고 쉽게 발..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 이번 문제는 dp문제로 제목이 정말 맘에 든다. 퇴사까지 N일을 앞두고 있는 백준이에게 상담 시간과 금액이 주어졌다. 퇴사까지 최대한 많은 상담 비용을 찾는 문제이다. 이 문제에는 한 가지 경우의 수가 존재한다. 예제 1번을 살펴보면 다음과 같다. 1일에 예약된 상담의 시간은 3일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 수 있다. 2일에 예약된 상담의 시간은 5일이다. 즉, 7일차가 되는 날에 상담 비용 20을 얻을 수 있다. 3일에 예약된 상담의 시간은 1일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이번 문제는 dp 문제로 설명이 너무 어렵게 되어있다. 간단하게 설명하자면 문제의 조건은 "인접한 집끼리 색이 겹치면 안된다."이다. 모든 dp문제는 점화식만 찾으면 쉽게 해결할 수 있다. 1번 예제를 보면서 점화식을 찾아보겠다. 1번 예제에서 최소값만 찾아서 누적합을 하면 다음과 같다. 최소값만 찾아서 진행했더니 문제의 조건 "인접한 집끼리 색이 겹치면 안된다." 를 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 해당 문제는 dfs, bfs 어떤 방법을 사용하던지 풀리는 문제인데 필자는 bfs를 이용해서 풀었다. 서로 연결된 컴퓨터를 저장하기 위해 int형 배열 map을 생성해주고, 해당 배열에 map[출발지][도착지] = 1, map[도착지][출발지] = 1을 입력해준다. for (int i=0; i

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 이번 문제는 기본적인 오름차순 정렬로는 해결할 수 없기 때문에 Arrays.sort() 메서드에서 Comparator를 구현해야한다. https://sookr5416.tistory.com/151 [백준]JAVA - 1931번: 회의실배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) ..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 풀이 문제를 보자마자 '2'로 무언가를 해야한다는 걸 알았다. 하지만 쉽게 찾을 수가 없었고 이것저것 해보다가 2진수를 발견했다. 우선 숫자 N을 Integer.toBinaryString(N)을 이용해서 2진수로 변경해주면 된다. String binary = Integer.toBinaryString(N); 이 문제의 핵심은 2진수로 변경된 숫자 '1'의 개수를 보면 된다. 예제 2번에서 숫자 N(13)..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 최근에 풀었던 미로탐색(2178번), 숨바꼭질(1697번) 문제와 동일한 유형이다. 이 문제를 풀어보기 전에 먼저 풀어보는 걸 추천한다. 위 문제를 풀었으면 bfs 방법에 대해서는 확실히 이해했다고 가정하고 간단하게 설명하겠다. 이번 문제는 익은 토마토를 기준으로 상하좌우 한 칸씩 모든 토마토를 익혀야하는 문제이다. 즉, bfs를 중간에 끊지말고 끝까지 돌려야한다는 의미이다...

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해당 문제는 (0, 0)에서 출발해서 (N, M)까지 최단 경로를 구하는 bfs 문제이다. 서로 인접한 칸만 이동할 수 있으며 1은 이동할 수 있는 칸, 0은 벽을 의미한다. 예제 1번을 보면서 문제를 이해해보겠다. 예제 1번의 최단 경로를 그려보면 위와 같다. 이러한 유형의 문제는 대부분 입력 값을 넣어줄 Map 배열과 방문 여부를 판단하는 visited 배열 두 가지가 필요하다. int[][] map = new int[N+1..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 최근에 풀어본 포도주 시식 문제(2156번)와 거의 똑같아서 점화식을 바로 찾을 수 있었다. 이 문제에서 제공하는 조건은 총 3가지이다. 1. 한 계단 혹은 두 계단을 오를 수 있다. 2. 연속된 3개의 계단은 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야한다. 쉽게 생각해서 i번째 칸에 대해서 두 칸 전(i-2) + 현재 칸(i) 와 세 칸 전(i-3) + 한 칸 전(i-1) + 현재 칸(i)를 비..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 처음엔 dfs를 이용해서 접근했지만 시간을 구하는 게 어려워져서 bfs로 접근했다. 문제에서 제시된 수빈이가 이동하는 방법은 총 3가지이다. 1. n+1 2. n-1 3. 2n 위 방법으로 1초마다 한 번씩 이동할 수 있다. 예제를 통해서 문제를 차근차근 이해해보겠다. 1. 초기 상태 (0초) 2. 1초 수빈이가 이동할 수 있는 곳은 n+1 → 6 n-1 → 4 2..