두부의 코딩일기

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 으로 사라지..

https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 풀이 문제를 읽은 직후에 이해가 잘 되지 않았다. 문제 내용은 아래와 같다. 1. 가로 x 세로 크기의 map에 램프가 있다. 2. 각 열의 맨 아래에 해당 열의 램프를 단 번에 키고 끌 수 있는 스위치가 존재한다. 3. 마지막 입력에 스위치를 누를 수 있는 횟수 K가 주어진다. 스위치를 K번 눌러서 각 행의 모든 램프가 켜진 행을 최대한 많이 만들면 된다. 예제 1번을 보면서 문제를 풀어..

대학교 교과 과정에서 들어봤을 법한 시간 복잡도는 대체 무엇일까? 필자도 최근에 알고리즘 문제를 많이 접하면서 다양한 알고리즘 구현 방법에 대해서 알아가고있다. 알고리즘 문제를 해결할 때의 핵심이 바로 시간 복잡도다. 시간 복잡도란 입력값의 변화에 따라 연산을 실행할 때 걸리는 시간을 말하는 것으로 시간 복잡도가 낮을 수록 효율적인 알고리즘이라고 할 수 있다. 시간 복잡도 표기법 Big-O (빅-오) : 최악 Big-Ω (빅-오메가) : 최고 Big-θ (빅-세타) : 평균 시간 복잡도를 표기하는 방법에는 위와 같이 총 3가지가 있다. 빅-오 표기법은 최악의 경우를 고려한다. 즉, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 생각한다. 어떠한 프로그램이든 최악의 사태를 미리 방지하고 고려해야하기 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 기본적인 bfs 에 간단한 조건만 추가하면 해결 할 수 있는 문제이다. 시작점 (0, 0) 에서 도착점 (N, M) 으로 갈 수 있는 최단 거리를 구하면 된다. Position 클래스를 생성할 때 x 좌표, y 좌표, 거리, 벽을 부셨는지 여부를 함께 저장할 수 있도록 선언한다. public static class Position { int x; // x 좌표 int..

정적 (Static) 메서드 정의 Java에서는 Static 변수와 메서드를 만들 수 있는데, 이를 정적 필드와 정적 메서드라고 부르며 이 둘을 합쳐서 정적 멤버(클래스 멤버)라고 합니다. 정적 필드와 정적 메서드는 객체(인스턴스)에 소속된 멤버가 아니라 클래스에 고정된 멤버이므로 클래스 로더가 클래스를 로딩해서 메서드 메모리 영역에 적재할 때 클래스별로 관리합니다. 따라서 클래스의 로딩이 끝나는 즉시 바로 사용할 수 있습니다. [장점] 1. static 키워드를 붙이면 메모리 할당을 딱 한 번만 하게 되어 메모리 사용에 이점을 볼 수 있음. 그렇기에 항상 값이 변하지 않는 경우라면 static 키워드를 사용하는 것이 좋음 2. static으로 설정하면 같은 곳의 메모리 주소만을 바라보기 때문에 stat..