Algorithm
-
[백준 1261 - JAVA] 알고스팟Algorithm 2020. 11. 9. 19:13
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 방향을 맞게 잡았으나 조건을 잘못 넣어서 메모리 초과가 2번 났었다. 다익스트라인줄 몰랐으나 풀고보니 최소 횟수를 따라가며 갱신할 수 있을 때 큐에 삽입하는 다익스트라 방식으로 잘 풀었었다ㅎㅎ... 풀이 방법 벽을 뚫은 횟수(이하 cnt)를 저장할 2차원 배열(ans) 을 생성하고 큰값으로 초기화한다. 초기 장소인 0, 0 cnt는 0으로 배열을 만들어 cnt가 기준인 우선순위큐에 넣는다. * 처음 장소는 항상 뚫려있다. 큐가 빌때까지..
-
[백준 3108 - JAVA] 로고Algorithm 2020. 11. 9. 18:28
3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다! 이삭이가 BFS를 이용해서 컬러링을 해보려했다는 것에서 아이디어를 얻어 풀었던 문제다. 일반적인 BFS로 풀경우 하나의 직사각형안에 겹치지 않게 딱맞게 직사각형이 들어갈 경우 겹친다고 체크하는 문제가 발생한다. 나는 직사각형을 그리면서 겹칠 경우 FindSet을 이용해 집합을 확인하고, 같은 집합이 아닐 경우 ans에서 1을 빼주도록 구현했다. 가운데 영점이 존재하는 좌표계이기 때문에 500을 더해서 배열에 저장..
-
[SWEA 3234 - 준환이의 양팔저울]Algorithm 2020. 11. 9. 18:27
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. DFS를 이용하여 순열을 구현하는 문제다. 나는 올리는 과정에서도 오른쪽이 왼쪽보다 무게가 적어야 한다는 것을 생각하지 못해서 2번정도 fail했다. DP를 이용하지 않고 순열로 구현했기 때문에, StringBuilder와 매개 변수로 전달해주어야 시간 초과가 나지 않는다. 풀이 방법 dfs를 이용해서 순열을 구현한다. 아래 두가지 경..
-
[SWEA 4193 - JAVA] 수영대회 결승전Algorithm 2020. 11. 9. 18:25
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성이를 우승시키기위한 최단 경로의 시간을 출력하자! 신호등 문제로 BFS에 현재시간과 소용돌이를 건널 수 있는 시간을 비교해서 큐에 넣어준다. 소용돌이의 시간이 일정하기 때문에 신호등이나 견우와직녀보다는 비교적 쉬운 문제다. 풀이 방법 시작점을 큐에 넣어준다. 큐 사이즈를 받아서 사이즈 만큼 돌아준다 (시간 체크) 소용돌이를 만날 경우 건널 수 없으면 다시 큐에 넣어준다. 2번을 체크해서 BFS를 구현할 경우 visit배열을 int형으로 해줄 필요가 없다 (메모이제이션 불필요) import java.io.*; import java.util.*; public cl..
-
[백준 1726 - JAVA] 로봇Algorithm 2020. 11. 9. 18:22
1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력하자! 아래 사항과 방문 처리만 주의한다면 문제없이 풀 수 있다. 방향이 동서남북 순서 시작점과 도착점이 같을 수 있다 -> 그러면 답이 0 2칸 이상 이동시 이동중 벽을 만날 경우 이동할 수 없다. 풀이 방법 입력받는 시작, 도착 위치가 1부터 이기때문에 1을 빼준뒤 저장한다. 시작점을 넣고 BFS를 시작하고, 방문 배열은 위치에 방향을 포함하여 3차원으로 처리한다. 이동 명령 먼저 수행하고, ..
-
[백준 9019 - JAVA] DSLRAlgorithm 2020. 11. 9. 18:19
9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 숫자A에서 숫자B로 변환하기 위해 필요한 최소한의 명령어 나열을 구하자! bfs에 대한 개념을 잘 잡고 있다면 간단하게 풀 수 있다. 제출 후 정답율이 올라가는게 삐끄덕 거리면서 느려서 당황했지만 무사히 통과! ✧ʕ̢̣̣̣̣̩̩̩̩·͡˔·ོɁ̡̣̣̣̣̩̩̩̩✧ 풀이 방법 숫자와 문자열을 가진 Number클래스를 이용해 bfs를 수행한다. 큐에 숫자A를 넣고 시작한다. DSLR을 순차적으로 실행 후, 숫자를 비교하여 숫자B와 같을 경우 문자열을 반환한..
-
[SWEA 4727 - JAVA] 견우와 직녀Algorithm 2020. 11. 9. 18:12
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 견우가 까마귀와 까치의 도움으로 최대한 빠르게 직녀에게 가는 방법을 찾아내자! BFS에 여러가지 조건을 적용한 문제로, 예전에 풀었던 신호등과 비슷한 문제다. 신호등은 추후에 업로드시 링크를 달아야겠다! 문제를 읽기가 힘들고, 조건을 이해하는게 힘들었다…. 풀이 방법 BFS를 돌면서 아래의 조건을 만족시킨다. 방문처리는 메모이제이션으로 가장 짧은 시간을 저장하여 확인한다. 오작교는 시간이 T라면 T의 배수에 건널 수 있다. 견우는 절벽을 연속으로 건널 수 없다. 교차하는 곳에는 오작교를 만들 수 없다. 0인 곳 (M인 오작교)는 한 개만 만들 수 있다. impor..
-
[백준 2887 - JAVA] 행성터널Algorithm 2020. 11. 9. 18:09
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다! 간선을 찾고 MST로 연결하는 것은 쉽지만, 행성의 개수가 100,000개로 시간초과 혹은 메모리 초과가 발생하는 문제다. 나같은 경우에도 메모리 초과를 3번 겪고난 후 다른 블로그를 참고하여 문제를 해결했다. 풀이 방법 각 행성의 Index와 x, y, z를 저장하고 Union-Find에서 사용할 배열을 초기화한다. 행성들의 거리를 계산하여 간선으로 PQ에 삽입한다. ..