매일 성장하자!!

문제 풀이 이 문제는 dp문제로, 바텀업(반복문)을 통한 메모이제이션으로 풀수 있습니다. 큰 문제를 작은문제로 나누는데 항상 결과가 같기 때문입니다.(반대로 큰문제를 풀기위해 작은문제를 사용하는 것이 문제가 없다라고 생각해도 좋습니다.) 무슨말이냐면, 미지의 번호인 i번째에 포도주를 먹는데 i - 1, i - 2 ...이전의 포도주를 먹는 최대값이 사용될수 있다는 의미입니다. 저는 항상 dp문제를 보면 미지의 번호인 i번째의 최대값을 구하는데 어떤 이전의 값들이 사용될까를 생각합니다. 이 문제는 '연속된 세개의 포도주를 먹을수 없다'라는 제한조건만 잘생각해보면 됩니다. i - 3i - 2i - 1i 안먹음먹음먹음 안먹음먹음 안먹음 그렇다면 이런식으로 세가지 경우로 나눌수 있습니다. 표에 입..

문제 풀이 맨 위에서부터 한 레벨씩 내려가면서, 왼쪽 아래, 왼쪽 오른쪽의 합을 더하며 dp 테이블에 값을 저장하면 된다. 높이는 최대 500이고, 내려가면서 현재 높이의 개수 * 2만큼 탐색하므로(2 + 4 + 6 + 8 + ... + 1000) 시간초과 날 걱정은 안해도된다. 물론 문제에서 풀라는 것과같이 이미 값이 있으면 최대값으로 dp 테이블을 갱신해 나가며 풀면된다. 반복문을 이용한 bottom up으로 dp테이블에 값을 적어가며 메모이제이션을 구현했고 해당 메모된 값을 계속 업데이트하며 문제를 풀었다. 나는 ArrayList를 이용했다. 코드 package baekjoon.DP; import java.io.BufferedReader; import java.io.IOException; impor..

문제 풀이 단순 bfs만으로 상하좌우 방문의 순서를 정해준다해서 같은 거리에 가장위쪽, 가장왼쪽의 먹이를 먹는다는 보장이 없다. 이 아이디어를 떠올리지못해 단순 bfs탐색 순서만으로 (위 -> 왼쪽 -> 오른쪽 -> 아래) 고집하여 풀다보니 문제를 푸는데 삼일을 소요했다. 왜 안될까? 직관적으로는 될거같지만, 현재 같은거리의 먹이를 기준으로 하지 않고 nextX, nextY의 위치를 기준으로 위 왼쪽 오른쪽 아래를 탐색하므로 잘못되었다. 현재 current 위치를 기준으로 먹을수있는 먹이중 가장 가까우면서 가장 위에있고 가장 왼쪽에있는 한먹이를 골라야한다. 그렇게 하기 위해선 일단 현재 위치에서 Queue를 이용해 그래프를 탐색하며(BFS) 먹을수있는 먹이를 모두 List에 넣는다. 그다음 List에서 ..

continuous memory allocation은 프로세스가 연속적으로 메모리에 적재되는것을 의미한다. 그와는 다르게 프로세스가 연속적으로 메모리에 적재되지 않을수도 있다. 이를 Non-continuous memory allocation이라한다. 프로세스가 연속적으로 메모리에 할당되지않고 블럭단위로 여러개로 쪼개서 할당될수 있다면 메모리를 더 효율적으로 사용할수 있을것이다. 그리고 사용되지 않는 블럭(프로세스를 블럭단위로 여러개 나눈것)은 swap device(disk)에 저장하니 메인메모리만 사용할때 보다 더 큰 용량을 관리할수 있다. Non-continuous memory allocation을 통해서 가상메모리라는 개념이 존재한다. 좀더 자세히 알아보자. Virtual Memory(Storage)..

문제 풀이 그리디 알고리즘으로 문제자체 푸는법은 어렵지않으나 나는 너무 안일하게 생각했던 나머지 2번 틀렸다. 그리디 알고리즘 자체가 '이 문제는 그리디 알고리즘으로 푸는 것이다'라는 것을 깨닫는게 어려운거지, 깨닫고나면 푸는법은 어렵지 않은 것 같다. 하나의 편집은 연속된 줄을 그룹으로 탭을 하나 추가하거나 삭제할수 있다. 이 편집의 횟수를 최소화하라는 문제이다. 일단 입력되는 두줄의 차이를 먼저 계산했다.(모두 0 으로 바꾸는게 목적이므로) 4 5 4 5 5 1 5 0 14 -1 5 4 가 된다. 일단 한번의 편집에 탭을 추가하거나 뺄수 있으니 음수 양수로 나눠야겠다는 생각을 했다. (4) (-1) (5, 4) 로 나뉘게 된다. 한번의 편집은 여러줄을 그룹으로 선택할수 있기에 여러줄을 ..

문제 3차원 토마토 상자의 모든 토마토가 익는 최소 일수를 구해라. 풀이 2차원과 다른점은 갈수있는 경로가 위, 아래 2개 더 는것 뿐이다. 그 이외에는 다른게없다. 가중치 없는 그래프에서 최소일수이므로 bfs로 풀면 쉽게 풀수있다. 코드 package baekjoon.그래프탐색; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main7569 { static int M, N, H; static int[][][] board; static boolean[][][] visited; static List okTomatoes = new ..

운영체제가 어떻게 메모리를 관리하는지 알아보자. 그전에 먼저 메모리에 대한 용어들 부터 알고 가자 메모리(기억장치)의 종류 레지스터는 cpu core내부에 존재하고, 캐시는 cpu내에 존재하는걸 확인할수있다.(그림에서) 메인메모리와 보조기억장치는 cpu내부에 없고 외부에 존재한다. 즉, 레지스터, 캐시는 HW(cpu)가 관리하고 메인메모리, 보조기억장치는 SW가 관리한다. 메모리(기억장치)의 계층구조 메모리는 보조기억장치 -> 메인 메모리 -> 캐시 -> 레지스터로 데이터를 전송하는 계층구조로 존재한다. 알아야할 두가지 용어 block : 보조기억장치가 주기억장치(메인메모리)로 데이터를 전송하는 단위(1 ~ 4KB) word : 주기억장치(메인메모리)가 레지스터로 데이터를 전송하는 단위(16 ~ 64bi..

좋은 객체지향 시스템을 만들기 위해선 객체들이 어떻게 커뮤니케이션을 하냐에 달렸다. 이 커뮤니케이션을 하는 방법을 메시지라하며 메시지는 객체의 책임을 유발한다. 메시지가 얼마나 중요한지 알아보자. 자율적인 책임 자율적이란 스스로 의지를 가지고 있어 스스로 판단할수 있다는 의미이다. 객체는 메시지를 수신받아야만 책임을 수행한다. 이 책임은 수신받은 객체 즉, 수신자가 자신의 의지와 판단에 맞게 책임을 수행해야한다. 이렇게 객체가 얼마나 자율적인 책임을 가지고 있느냐가 객체지향 어플 전체의 품질을 결정한다. 그렇다면 자율적인 책임이 뭔지 보다더 자세히 알아보자. 자율적인 책임 예시 선생님이 학생에게 공부를 시켜야하는 상황을 가정해보자. 선생님 학생에게 '공부해'라는 메시지를 송신해야 학생은 메..

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 풀이 일단 가중치없는 그래프에서 최단 경로이므로 BFS로 풀어야하는 것은 눈치를 챘다. 그런데,,, 쉽게 풀줄..

문제 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다. 버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다. 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시..