본문 바로가기

Algorithm/SW Expert Academy18

[SW Expert] [모의 SW 역량테스트] 2117번 홈 방범 서비스 (Java) SW Expert [모의 SW 역량테스트] 2117번 홈 방범 서비스 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 마름모 구역 탐색 때문에 꽤나 고민했던 문제이다. 문제는 그렇게 어렵지 않다. 모든 경우의 수를 다 따져보면 되는 브루트 포스 문제이다. 프로그래머스의 자물쇠와 열쇠와 비슷한 문제이지만, 그보다 좀 더 복잡하다고 생각한다. 우선 마름모가 도시 밖으로 나갈 수 있으므로, 상하좌우로 패딩을 줘서 index가 도시 밖으로 나가지 않게끔 한다. 여기서는 전체 도시를 100 x 100 크기로 선언하여 (40,40)부터 입력을 받았다. 마름모를 탐색하는 방법은 여러가지가 있지만.. 2020. 2. 16.
[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.
[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.
[SW Expert] 4615. 재미있는 오셀로 게임 (Java) 문제 링크 : [SW Expert] 4615. 재미있는 오셀로 게임 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 1. N 값에 맞춰 보드판을 생성한다. 2. 입력받은 x, y 좌표에 바둑알 놓는다. 3. 놓은 위치에서 상, 하, 좌, 우, 대각선 총 8개 위치를 탐색, 내 바둑알이 있는지 확인한다. 4. 내 바둑알이 있다면 어디까지 바둑알을 뒤집을지 위치 확인한다. 5. 확인한 위치까지 바둑알을 뒤집는다. 후기 어린 시절에 많이 했었던 오셀로 게임을 구현하는 문제였다. 문제를 읽자마자 어떻게 구현해야 할지 감은 바로 왔지만, 구현하는 데 있어서는 꽤나 까다로웠다. 총 8방향의 모든 부분을 체크해줘야.. 2020. 1. 1.