Algorithm (117) 썸네일형 리스트형 [백준] JAVA - 20058. 마법사 상어와 파이어스톰 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 생각 1. 상태배열을 시계방향으로 90도 회전한다. 2. 인접한 얼음 영역이 3개 미만일 경우 현재 위치의 얼음을 -1 감소시킵니다. (이때 바로바로 값을 변경해주면 다른 값들에 영향이 가기때문에 변경할 좌표값을 큐에 넣어 한번에 처리했습니다.) 3. Q번만큼 1번~2번 작업을 반복한뒤 가장 큰 얼음영역을 BFS로 찾는다. 남아있는 얼음의 합을 구한다. 시계방향으로 90도 회전.. [백준] JAVA - 17471. 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 생각 선거구를 두 그룹으로 나누고 나눈 그룹들은 해당 그룹 내부에서 서로 연결되어 있어야 합니다. 문제 풀이의 큰 흐름은 다음과 같습니다. - 두 그룹으로 나누는 모든 경우를 구한다. - 나눈 두 그룹이 각각 내부에서 서로 연결되어있는지 확인한다. - 두 그룹이 해당 그룹 내부에서 모두 서로 연결되어있다면 두 그룹의 인구 수 차이를 계산한다. 1. 두 그룹으로 나누는것은 재귀함수를 사용했습니다. 1 ~ N/2개가 될때.. [SWEA] JAVA - 1953. [모의 SW 역량테스트] 탈주범 검거 생각 파이프는 상하좌우 네가지 방향성을 가지고 있습니다. 파이프가 가질 수 있는 방향 상태의 조합을 비트마스킹으로 표현하여 상하좌우 -> 1111 과 같이 나타냈습니다. 즉, 상 : 1000, 하 : 0100, 좌 : 0010, 우: 0001 로 나타내었고 파이프의 형태에 따라 OR 연산으로 갈 수 있는 방향에는 비트를 1로 설정하여 초기화 시켰습니다. 탈주범의 시작위치로부터 주어진 시간까지 어떤 칸을 갈 수 있는지는 BFS 를 사용하여 문제를 풀었습니다. BFS 내부에서 다음칸으로 갈수있을지 체크를 할 때 파이프의 연결성을 체크하는 메소드를 만들었습니다. 갈려고 하는 칸과 현재의 방향값 비트를 파라미터로 받아 다음 칸으로 갈수있는지를 체크해줬습니다. 현재 방향값 비트가 1000일때 위쪽 방향을 나타내므.. [백준] JAVA - 2564. 경비원 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 생각 (0,0)에서 시작하여 직사각형을 시계방향으로 둘레를 쭉 펼쳐줬다고 생각하여 거리를 측정해줍니다. 상점의 좌표가 x이고 북쪽이면 거리는 x, 동쪽이면 거리는 C+x, 남쪽이면 C+R+(C-x), 서쪽이면 C+R+C+(R-x) 입니다. (0,0) ~ 상점거리와 (0,0) 동근이의거리를 시계방향만큼 측정해줬기 때문에 반시계방향으로 거리를 측정할때는 둘레 - 시계방향으로 측정한 거리값입니다. 각 상점의.. [백준] JAVA - 17144. 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 생각 미세먼지의 확산과, 공기청정기가 작동하는 것을 모두 함수로 구현했습니다. 1. 미세먼지 확산 우선, 미세먼지의 확산은 모두 동시에 진행되기 때문에 BFS를 사용하여 구현했습니다. 다음으로 확산된 미세먼지들이 누적하는것은 따로 배열에 담아 저장시키고 나서 확산이 끝나면 한번에 누적시켰습니다. 미세먼지들이 동시에 확산되고 확산되는 양들을 어떤 타입으로 누적시켜야 할 지 한참 고민하다가 Dust.. [백준] JAVA - 7576. 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 생각 BFS를 사용하고 BFS가 퍼져나갈때마다 큐의 원소에 들어가는 day를 1씩 증가시켜서 걸린 시간을 나타내도록 했습니다. map의 원소를 마킹하는것보다는 이 방식이 더 나은것같습니다. BFS의 시작점이 다수인경우에는 큐안에서 queue.size()만큼 반복문을 다시 돌게 해줍니다. 이렇게 하면 특정 정점으로부터 시작되는 너비 우선 탐색이 동시에 실행되게 구현할 수 있습니다. .. [SWEA] JAVA - 1249. 보급로 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 생각 (0,0) -> (N-1, N-1)로 갈때 최소 비용으로 가는 비용을 찾는 문제입니다. 최소 비용을 찾는 문제이므로 경로가 단순하게 좌 -> 우 or 위 -> 아래 방향이 아니라 돌아서 갈 수 있기 때문에 BFS + 우선순위 큐를 사용하여 최소 비용을 가지는 지점을 가장 먼저 탐색하도록 했습니다. 1. 우선순위 큐를 생성하고 시작 위치를 넣어줍니다. 2. 큐가 빌때까지 3~5번 작업을 반복합니.. [SWEA] JAVA - 1251. 하나로 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 생각 모든 섬들을 해저터널로 연결할때 최소비용으로 연결할때의 최소비용을 출력하는 문제입니다. 즉, 그래프에서 최소 비용을 찾는 문제로 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 MST를 구현하는 문제였습니다. 크루스칼 알고리즘을 사용하여 풀었습니다. 저는 섬들을 연결할 때 조합을 사용하여 가능한 모든 경우를 미리 탐색하도록 했는데 MST가 간선 기반의 greedy 알고리즘이므로 이렇게.. 이전 1 2 3 4 5 6 7 8 ··· 15 다음
