본문 바로가기

전체 글151

[JAVA] 백준(14442) - 벽 부수고 이동하기 2 (BFS) www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽을 최대 K 개 부술수 있다. 벽을 부수지 않은 경우 / 1개 부순 경우 / 2개 부순 경우 .... / K개 부순경우 경우를 나눠서 방문 체크를 하며 BFS 하면된다. 평범한 2차원 배열의 BFS라면 2차원 배열로 해당 위치를 방문 체크하면 되지만 경우를 나눠서 방문 체크하는 이유는 다음과 같다. 만약 ( x, y ) 라는 위치에 먼저 방문했다고 해서 최단거리임을 보증할 .. 2020. 10. 12.
[JAVA] 백준 - 돌그룹 12886 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net # 2개의 그룹의 돌 개수를 알면 나머지 한 그룹의 돌 개수는 자동으로 정해진다. 따라서 2차원 배열로 방문체크를 해도된다. 예를 들어, { 4, 5, 6 } 의 돌 그룹이 있다고 하자. 그러면 check[4][5] 만 하면된다. 반대로 check[5][6]을 했다면 check[4][5]는 필요없다. 또한 순서도 상관없다. check[4][5] 를 하거나 check[5][4]를 하거나 똑같다. 왜냐면 4,5.. 2020. 10. 11.
[일지] 의존관계 주입의 필요성 # 객체 지향 설계에서 의존관계 class Car{ // Engine 은 인터페이스 & SuperEngine 은 Engine의 구현체 private final Engine engine = new SuperEngine(); ... } 위와 같은 코드가 있다고 가정해보자. 자동차는 반드시 엔진이 필요하다. 그래서 처음 설계할 때, 자동차는 엔진이라는 인터페이스에 의존하도록 설계하였다. 인터페이스에 의존하는 것처럼 보이지만 실제는 그렇지 않다. 아래 그림처럼 되기를 원하지만 실제는 아래와 같다. 만약 울트라 엔진으로 고친다면 아래처럼 Car의 코드를 수정해야한다. class Car{ // Engine 은 인터페이스 & UltraEngine 은 Engine의 구현체 private final Engine engi.. 2020. 10. 11.
[JAVA] 백준 연구소 - 14502 ( BFS + DFS) www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net # 벽은 어디다가 설치하는가?? 반드시 3개만 설치해야한다고 조건에 명시되어 있다. 최대 배열의 너비가 8*8 = 64 이므로 여기서 3개를 선택하는 최대 모든 경우의 수는 41644 이다. 완전 탐색으로 3개를 선택해도 무리가 없다. 완전탐색이 가능하면 더이상 생각할 필요가 없는 듯하다. 벽 3개를 선택하는 로직은 DFS를 선택한다. static void dfs(int idx,int cnt){ if(idx == tota.. 2020. 10. 11.
[JAVA] 프로그래머스 - 단체사진 찍기 ( 카카오 코드 2017 본선 ) 문제를 처음에 잘못이해해서 왜 3648 가지가 나오는지 고민했는데 그냥 단순한 순열 문제였다. # 3648 인 이유 N 과 F 는 이웃하면서 R과 T 사이에 3명이상 사람이 오는 경우의 수를 묻는다. 1) R 과 T사이에 NF포함 3명이 있는 경우 = 4! * 4C1 * 2! * 2! * 2! = 768 2) R 과 T 사이에 NF를 포함하지 않는 3명이 있는 경우 = 3! * 4C3 * 3! * 2! * 2! = 576 3) R 과 T 사이에 NF 포함 4명이 있는 경우 = 3! * 4C2 * 3! * 2! * 2! = 864 4) R과 T사이에 NF를 포함하지 않는 4명이 있는 경우 = 2! * 4! * 2! * 2! = 192 5) R 과 T 사이에 5명 있는 경우 = 2! * 4C3 * 4! * .. 2020. 10. 9.
[JAVA] 백준 - DSLR 9019 ( BFS) www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 클래스 Pair 를 계속 생성해서 그런지 모르겠는데 메모리 엄청 쓴다.. 쓰지 않으면 더 빠르게 구동 되지만 직관적으로 이해하고 문제 풀이가 빨라서 Pair 클래스를 만들어서 쓰고 있다. # 문제의 관건인 D S L R 을 구현하기 //D nx = (x*2)%10000; //S nx = x==0?9999:x-1; //L nx = (x%1000)*10 + (x/1000); //R nx = (x/1.. 2020. 10. 8.
[JAVA] 백준 - 데스나이트 (BFS) www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 가장 기본적인 로직만 있는 문제. 상하좌우가 아니라 이동할 수 있는 다음 장소가 6군데라는점만 조심하면 된다. 또한 한번 방문한 곳을 또 방문하여 최단거리를 갱신하는 일은 없으므로 2차원 배열로 방문 체크를 해도된다. import java.util.LinkedList; import java.util.*; class Main{ stat.. 2020. 10. 8.
[JAVA] 백준 - 뱀과 사다리 게임 (BFS) www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀으로 가면 무조건 손해라고 생각했지만 아니다. 만약 아래처럼 테스트 케이스를 주어진다고 해보자. # 뱀을 타야만 최단거리를 만드는 테스트 케이스 2 1 2 50 49 100 51 48 1. 1을 던져서 2번으로 간 다음 사다리를 타고 50으로 간다. 2. 1을 던져서 51번으로 간 다음 뱀을 타고 48로 간다. 3. 1을 던져서 49번으로 간 다음 사다리를 타고 .. 2020. 10. 8.
[JAVA] 백준 구슬탈출 2 - 13460 ( DFS & 구현) www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구현 + dfs 문제 1. 빨간 구슬과 파란 구슬은 동시에 같은 위치에 있을 수 없다.(핵심구현) 구현의 첫번째 난관이다. 아래처럼 방향을 정하고 int[] dx = {-1,1,0,0}; int[] dy = {0,0,-1,1}; 기존 위치가 [x,y] 라면 다음 위치는 [ x + dx[i], y + dy[i] ] 이다. (이때 i는 0부터 3까지 중 하나의 숫자.. 2020. 10. 1.

티스토리툴바