두부의 코딩일기

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 이번 문제는 조건이 많아서 고민할 게 많았다. 구동 순서는 아래와 같다. 택시 위치로부터 가장 가까운 손님을 찾는다. (findPerson) - bfs 가까운 손님의 목적지까지 이동 (goTaxi) - bfs 위 내용을 반복한다. 1. 택시 위치로부터 가장 가까운 손님을 찾는다. public static void findPerson(int x, int ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음에 문제를 잘 못 이해해서 꽤 오랫동안 고민했다. 우선 모든 행과 열을 한 줄로 나열해서 체크해야 한다. 예를 들어, 위 그림처럼 6x6 행렬이 있다면 행 6번, 열 6번 총 12번의 체크를 해야 한다. for (int i=0; i 1) { return false; } 이젠 경사로를 놓았을 때의 경우만 생각하면 된다. 경사로를 놓았을 때 생기는 경우의 수는 2가지이다. 오르막 길 내리막 길 오르막 길, 내리막 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에 이해하기 쉽게 설명이 잘 적혀있으니까 생략하겠다. 위 문제에서는 두 개의 일이 순서대로 이루어진다. 미세먼지 확산: 4방향으로 먼지가 확산된다. 공기청정기 작동: 위 칸과 아래 칸의 바람이 방향이 서로 다르며 한 칸씩 먼지를 밀어낸다. 미세먼지 확산은 dfs 혹은 bfs를 이해하고 있고 관련된 문제를 풀어봤다면 쉽게 해결할 수 있을 것이다. public static void Dust..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 기본적인 bfs 에서 말이 이동할 수 있는 경로만 신경써주면 된다. 말처럼 이동할 수 있는 기회는 K번으로 횟수가 제한되어있으며 벽을 넘을 수 있다. 시작점 (0, 0) 으로 출발해서 (w, h) 까지 최소한의 횟수로 도착하면 된다. 원숭이 상태와 말 상태일 때를 구분해서 돌려주면 쉽게 해결할 수 있다. 1. 원숭이 상태일 경우 1) 이미 방문을 했는지 여부 판단 (visit..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 5가지의 감시 카메라가 상우하좌로 돌면서 사각지대의 최솟값을 찾아야한다. 감시 카메라의 경우의 수는 아래와 같다. 1번 카메라: 4가지 2번 카메라: 2가지 3번 카메라: 4가지 4번 카메라: 4가지 5번 카메라: 1가지 예를 들어 1번과 2번 카메라가 하나씩 존재한다면 경우의 수는 4 x 2 = 8가지이다. 경우의 수를 다 돌려주기 위해서 완전탐색 dfs를 돌려준다. public..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 문제의 조건은 매우 간단하다. 0이 등장하면 전에 입력받았던 숫자를 지우면 된다. 또한, 0이 등장했을 땐 지울 수 있는 숫자가 있음을 보장했기 때문에 예외 처리를 해줄 필요도 없다. 문제를 푸는 방법은 2가지가 있다. 1. 스택 (Stack) 을 이용하는 방법 import java.io.*; import java.util.*; public class Mai..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 실버3 난이도의 구현 문제로 생각보다 오래 걸렸다... 문제를 시작하기에 앞서 시작 위치와 방향 전환에 대해서 고민해봐야 한다. 우선 왼쪽 그림처럼 (0, 0) 을 시작점으로 두고 시작하게 되면 숫자가 1씩 작아지고, 오른쪽 그림처럼 (N/2, N/2) 에서 시작하게 되면 숫자가 1씩 증가한다. 또한 나아가는 방향의 순서도 반시계 방향, 시계 방향으로 달라진다. 공통적으로 방향 전환에 대해서 ..

오라클에서는 함수 내의 인자값 중에서 최대값, 최솟값을 찾을 수 있는 함수를 제공한다. 최대값과 최솟값을 구하는 함수로 MAX 와 MIN 함수가 생각날텐데 사용 방법이 조금 다르다. MAX, MIN 은 검색 조건에 맞는 값 중에서 최대값, 최솟값을 찾는다. GREATEST, LEAST 는 여러 개의 열(Column)에서 최대값, 최소값을 찾고, 숫자가 아닌 문자열도 비교가 가능하다. GREATEST, LEAST SELECT GREATEST(100, 200, 300) AS GREATEST , LEAST(100, 200, 300) AS LEAST FROM DUAL; // 300, 100 여러 개의 인자값에서 최대값, 최소값을 뽑아올 수 있다. 위 쿼리의 GREATEST에선 300, LEAST에선 100이 출..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 풀이 브루트포스, 구현 문제는 개인적으로 너무 어렵다.. 나만의 팁이라고 한다면 dp처럼 공책에다가 써본 후에 로직을 어느 정도 파악하고 코딩을 시작한다. 위 문제의 조건은 아래와 같다. 범위는 세 자릿수 자릿수와 숫자가 같으면 스트라이크 자릿수가 다르고, 숫자가 같은 게 있으면 볼 그럼 이제 문제를 풀어보겠다. [1번 조건] 세 자릿수를 가진 자연수는 100 부터 999 이다. 하지만 중복된 숫..

자바에서 문자열을 처리할 때 대표적으로 String, Stringbuffer, StringBuilder 3가지를 사용한다. 위 3가지의 차이점은 무엇일까? String int, long, float, char, boolean과 같은 primitive 타입이 아닌 reference 타입의 참조형 변수로 한 번 할당된 공간이 변하지 않는 immutable 자료형이다. String str = "Hello "; str += "World !!!"; 위의 그림을 보면 본래 가리키고 있던 "Hello" 를 버리고 "Hello World !!!" 라는 값을 가지는 메모리 영역을 가리킨다. immutable 자료형의 특징으로 문자열을 수정하게 되면 기존에 있던 메모리 영역은 Garbage Collection 으로 사라지..