BangBang's Devlogs

https://programmers.co.kr/learn/courses/30/lessons/12899?language=java# 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 해결 방안 3진법의 응용과정이다. 3으로 나눴을때 나머지가 0인 경우를 처리해주면된다. (4가 되고 n-=1 해주는) 코드 // 124 나라의 숫자 class Solution { public String solution(int n) { String answer = ""; int rest = 0; w..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 DFS + 구현 문제이다. 처음 시간 초과나서 방법을 좀 바꿔서 다시 풀었다. 해결 방안 처음에는 전체 집List, 전체 치킨집List와 visited 배열을 사용하여 전체 치킨집 중 M개를 DFS 와 백트래킹을 이용하여 구현하였다. 하지만 거리를 구하는 과정에서 전체 집에서 전체 치킨집을 돌면서 M개에 포함되지 않는 경우도 조건을 통해 거르다 보니 시간 초과가 났다. ..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 문제 구현 문제이다. 해결 방안 map의 전체 크기는 101 x 101이 될 것이다. (전체 격자가 100x100 이므로) 1. 드래곤 커브의 갯수 N만큼 드래곤 커브의 정보들(x, y, d, g)을 받게 되는데 (drawDragonCurve() 함수 참고) 1.1. 각 드래곤 커브마다 g(세대)까지 map에 그려줘야한다.(드래곤 커브가 가지고 있는 꼭지점을 true로..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 문제 DFS + 구현(Simultation) 문제이다. 해결 방안 CCTV 클래스를 만들어서 각 CCTV의 y(row), x(col), kinds(cctv 종류), dir[](해당 cctv가 가진 방향) 정보를 가지고 있도록 하였다. 1. Main에서 사무실 공간 값(map[i][j])을 입력 받을 때 cctv 값(1~5)가 포함되면 List cctvs에 넣어주었다. 2. cctvs..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 문제 구현(Simulation) 문제이다. 해결 방안 문제 구성을 크게 1. 입력 받는 부분, 2. 각 톱니바퀴 회전 방향 입력에 따른 전체 톱니바퀴 회전 방향 구하기, 3. 회전 방향에 따른 각 톱니바퀴 상태 재설정, 4. 다 회전한 후 톱니바퀴 점수 합 구하기 로 4가지로 구성하였다. 1. 입력 받는 부분은 그냥 입력 받으면 되는 부분이라 넘어갑니다. 2. 각 톱니 바퀴 회전 방향 입..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 Simulation 문제이다. Queue를 사용하여 구현하다가 올라가는 경사에서 막혀서 다른사람 풀이를 참고하였다. 해결 방안 주어진 조건에 맞도록 구현하는 Simulation 문제이다. 1. 각 행과 열마다 지나길 수 있는 길인지 체크해서 갯수를 세준다. 2. 해당 행과 열을 1차원 배열로 만들어서 체크하기 쉽게 만든다. (checkPath()함수) 조건이 맞지 않는 경우 false를 리턴해준다. 코드 impor..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 DFS + 구현 으로 문제를 해결하였다. 해결 방안 전체적으로 보면 1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수와 2. 나눠진 팀의 점수 차이를 구하는 두가지를 구현해야한다. 1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수는 DFS 탐색을 이용하여 구현하였다. 기저사례가 N/2 일 때까지 DFS 탐색을 하며 N/2 개의 visited를 true로 만들어준다. caculateDi..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 문제 브루트포스 문제 인데 DFS 탐색을 이용하여 문제를 해결하였다. 해결 방안 숫자의 위치는 고정이고 연산자 우선순위도 무시하므로 숫자간 모든 경우의 연산자를 넣어 각각의 sum값들을 비교하여 최대 최소값을 구하는 문제이다. 덧셈, 뺄셈, 곱셈, 나눗셈의 갯수의 합이 N-1 개이므로 각각의 갯수들을 고려하여 DFS 탐색을 해주면된다. ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 DFS 문제라고 생각하고 풀었는데 stackoverflow가 자꾸 떠서 다른 사람 풀이 참고하여 풀었다. (알고보니 구현 문제) 해결 방안 문제에서의 로봇 청소기 작동 방법에 맞춰서 구현해주면 된다. while 두개를 이용하여 구현하였으며 코드를 보면 1, 2 조건에 따른 코드를 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOExce..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제 벽 3개 세우는 경우를 완전 탐색하고 벽이 3개 세워진 경우에 바이러스를 퍼트려서 최대 안전 구역 크기를 구해주는 문제이다. 생각보다 쉽게 풀려서 놀랐다. DFS + BFS 문제 해결 방안 1. 메인에서 지도값 입력받을 때 바이러스의 좌표를 저장할 수 있는 자료구조(여기서는 ArrayList 사용함)를 사용해준다. (나중에 BFS 탐색에서 Queue에 넣어줄 값) 2. DFS 탐색을 이용하여 벽이 3개..