본문 바로가기

전체 글129

[SW Expert] [모의 SW 역량테스트] 1949번 등산로 조성 (Java) SW Expert [모의 SW 역량테스트] 1949번 등산로 조성 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 최대 등산로의 길이를 찾는 dfs + 브루트 포스 문제이다. 각 위치에서 최대 K만큼 지형을 깎을 수 있다. K만큼 지형을 깎을 수 있다는 조건이 어렵게 느껴질 수 있으나, 그냥 최대 등산로의 길이를 찾는 로직을 K번 반복해주면 된다. 전체적인 흐름은 아래와 같다. 1. 2중 for문을 사용해서 map에서의 index를 하나 지정한다. 2. 해당 위치에서 0~K만큼의 지형을 깎는다. 3. 미리 받아둔 최고점의 위치에서 dfs로 탐색한다. 4. 2번에서 깎은 지형만큼 다시.. 2020. 2. 16.
[백준] 6087번 레이저 통신 (Java) 백준 6087번 레이저 통신 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. www.acmicpc.net 생각보다 오래 걸렸던 문제이다. 최소 개수의 거울을 사용해서 두 'C'를 연결하면 된다. bfs를 사용.. 2020. 2. 16.
[SW Expert] [모의 SW 역량테스트] 1953번 탈주범 검거 (Java) SW Expert [모의 SW 역량테스트] 1953번 탈주범 검거 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq bfs를 많이 해봐서 그런가 이제 이런 유형의 문제는 익숙한 듯하다. Queue에 탈주범이 위치해 있는 좌표값을 넣는다. 탈주범이 방문했던 곳은 다시 넣지 않으므로, 탈주범이 해당 시간동안 가장 멀리 갈 수 있는 곳의 좌표가 들어가게 된다. 본 문제에서는 특이한 조건이 있었는데, 파이프의 종류에 따라 갈 수 있는 곳이 달라진다. 파이프를 연결하기 위해서 해당 위치에서 파이프가 연결된 곳의 정보를 status로 지정해줬다. 북쪽부터 시작하여 시계방향으로 0, 1, 2, 3.. 2020. 2. 14.
[SW Expert] [모의 SW 역량테스트] 5656번 벽돌 깨기 (Java) SW Expert [모의 SW 역량테스트] 5656번 벽돌 깨기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo 정답률 보고 들어갔다가 큰 코 다쳤던 문제이다. dfs와 bfs를 함께 적용해야 한다. 구슬을 N번 쏠 수 있고, 최대한 많은 벽돌을 깨야 하기 때문에 모든 경우의 수를 확인해봐야 한다. 전체적인 흐름으로는, 0. 초기에 Queue에 int[][] map을 담는다. 1. Queue에서 map을 꺼낸 뒤, 0번째 행부터 우측으로 하나씩 움직이며 구슬을 떨어뜨린다. 2. 구슬이 떨어진 벽돌을 기준으로 깨질 수 있는 모든 벽돌을 제거한다. 3. 남아 있는 벽돌들을 밑으로 떨어뜨.. 2020. 2. 14.
[SW Expert] [모의 SW 역량테스트] 5650번 핀볼 게임 (Java) SW Expert [모의 SW 역량테스트] 5650번 핀볼 게임 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo 모의 SW 역량테스트 중 하나인 핀볼 게임이다. 어렸을 때 핀볼 게임을 해봤던 사람이라면 문제 이해하는 것은 쉬울 것이다. 게임판 안에는 총 5가지의 블록과 웜홀, 블랙홀이 들어 있다. 장애물에 부딪히며 움직이다가 블랙홀에 빠지거나 제자리로 돌아오면 게임이 끝나게 된다. 모든 경우의 수를 다 따져봐야 하는 브루트 포스 문제이다. 장애물이 없는 모든 구역에서 상하좌우로 핀볼을 움직여야 한다. 이번 문제에서 주요 함수로는 방향을 바꿔주는 changeDir 함수와 핀볼이 움직이.. 2020. 2. 13.
[백준] 1062번 가르침 (Java) 백준 1062번 가르침 : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다. www.acmicpc.net 은 브루트 포스, 시뮬레이션 문제이다. 입력으로 단어의 개수(N)와, 김지민이 가르치는 글자의 개수(K)가 주어진다. 문제에서 특이한 조건이 하나 있는데, 모든 단어는 "anta"로 시작되고 "tica"로 끝난다는 점이다. 따라서 a, c, i, n, t는 김지.. 2020. 2. 12.

티스토리툴바