이우의 개발일지

백준 12865번 평범한 배낭 문제https://www.acmicpc.net/problem/12865 문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.입력첫 줄에 물품의 수..

백준 2178번 미로 탐색 문제https://www.acmicpc.net/problem/2178  문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수..

백준 18870번 좌표 압축 문제 및 코드 풀이 문제수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.입력첫째 줄에 N이 주어진다.둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.출력첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 제한1 ≤ N ≤ 1,000,000-109 ≤ Xi ≤ 109예제 입력 1 52 4 -10 4 -9예제 출력 1 2 3 0 3 1예제 입력 2 61000 999..

백준 1074번  Z 문제한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다.입력첫째 줄에 정수 N, r, c가 주어진다.출력r행 c열을 몇 번째로 방문했는지 출력한다.제한1 ≤ N ≤ 150 ≤ r, c 예제 입력 1 2 3 1예제 출력 1 11예제 입력 2 3 7 7예제 출력 2 63예제 입력 3 1 0 0..

백준 2630번 색종이 만들기문제아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은..

백준 14940번 최단거리문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.입력지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.예제 입력 1 복사15 152 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1..

백준 7576번 토마토 토마토 문제풀이토마토 문제는 하루 동안 상, 하, 좌, 우에 있는 토마토들이 익게 되는데 며칠만에 익게 되는지 최소 값을 찾는 문제이다.상,하,좌,우 + 최소값을 얘기할 때 BFS를 자연스레 떠올리게 되었다. - 토마토 창고 크기는 M * N - M * N 크기의 창고에서 토마토의 각 상태 (1 : 익음, 0 : 안 익음, -1 : 존재 X) 를 저장한다. 만약 토마토가 익은 상태 (1) 이면 queue에 저장- queue에 저장된 값 중 front에 있는 값을 빼와서, 그 값의 상, 하, 좌, 우를 탐색한다. 탐색 조건으로는 0부터 m과 n 사이에 있어야하며, 상태가 0이여야 한다. - 만약 BFS를 다 돌고 나서, 0이 존재한다면 -1로 둘러쌓여있어서 탐색할 수 없다는 표시로 ..

DP, 다이나믹 프로그래밍이란? -> 하나의 문제를 단 한번만 풀도록 하는 알고리즘 설계 기법입니다. Why DP를 사용할까?그냥 사용하면 사실 재귀방식과 똑같이 사용할 수 있다. 하지만, 일반적인 코딩테스트 같은 경우 시간제한이 걸려있기 때문에 동일한 작은 문제를 여러번 풀면 무조건적으로 시간초과가 뜨게 된다.  예를 들어, 피보나치 수열을 그 예로 들 수 있다.#include int dp(int x){ if( x == 1) return 1; if( x == 2) return 1; return dp(x - 1) + dp ( x - 2); } 위 처럼 코딩을 하게 된다면, 50번째만 가도 굉장히 오래 걸리게 된다.  #include int d[100];int dp(int x){ ..