알고리즘 문제풀이/BOJ
-
BOJ 20056번 마법사 상어와 파이어볼 자바(java) 풀이 랭크 : 골드5 백준 20056번 마법사 상어와 파이어볼 문제 정리 NxN 크기의 격자 파이어볼 M개 i번 파이어볼의 위치(r, c), 질량 m, 방향 d, 속력 s 격자의 번호는 1~N 1번 행은 N번과 연결/ 1번 열은 N번 열과 연결 파이어볼은 8개의 방향을 가짐 파이어볼은 다음과 같이 이동한다. 7.1 자신의 방향 d로 속력 s 만큼 이동 7.2 이동이 끝난 뒤, 2개 이상의 파이어볼이 같은 칸에 있으면 다음 일이 일어남 - 같은 칸의 파이어볼은 모두 하나로 합쳐짐 - 파이어볼이 4개로 나누어짐 - 나누어진 파이어볼의 질량, 속력, 방향이 바뀜 - 질량이 0인 파이어볼은 소멸 K번 명령 후, 남아있는 파이어볼의 질량의 합 구하기 전체..
[시뮬레이션] 백준 20056번 마법사 상어와 파이어볼 :: 삼성 sw 역량 테스트 기출 (java)BOJ 20056번 마법사 상어와 파이어볼 자바(java) 풀이 랭크 : 골드5 백준 20056번 마법사 상어와 파이어볼 문제 정리 NxN 크기의 격자 파이어볼 M개 i번 파이어볼의 위치(r, c), 질량 m, 방향 d, 속력 s 격자의 번호는 1~N 1번 행은 N번과 연결/ 1번 열은 N번 열과 연결 파이어볼은 8개의 방향을 가짐 파이어볼은 다음과 같이 이동한다. 7.1 자신의 방향 d로 속력 s 만큼 이동 7.2 이동이 끝난 뒤, 2개 이상의 파이어볼이 같은 칸에 있으면 다음 일이 일어남 - 같은 칸의 파이어볼은 모두 하나로 합쳐짐 - 파이어볼이 4개로 나누어짐 - 나누어진 파이어볼의 질량, 속력, 방향이 바뀜 - 질량이 0인 파이어볼은 소멸 K번 명령 후, 남아있는 파이어볼의 질량의 합 구하기 전체..
2020.10.29 -
BOJ 16236번 아기 상어 문제 자바(java) 풀이 랭크 : 골드5 백준 16236번 아기 상어 문제 정리 NxN 크기의 공간 M마리의 물고기 아기 상어 1마리 한 칸에는 물고기가 최대 1마리 존재(없거나 1마리) 초기 아기상어의 크기는 2 1초에 상하좌우 한 칸씩 이동 자신의 크기보다 큰 물고기가 있는 칸 제외 모든 칸 지나갈 수 있음 자기보다 작은 물고기 먹을 수 있음, 크기 같으면 지나만 갈 수 있음 이동 결정 알고리즘 더 이상 먹을 수 있는 물고기가 없으면 엄마에게 도움을 청함 먹을 수 있는 물고기가 1마리면 그 물고기를 먹으러 감 먹을 수 있는 물고기가 1마리 보다 많다면, 거리가 가장 가까운 물고기를 먹으러 감 거리: 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 ..
[BOJ] 삼성 sw 역량 테스트 기출 :: 16236번 아기 상어 (java)BOJ 16236번 아기 상어 문제 자바(java) 풀이 랭크 : 골드5 백준 16236번 아기 상어 문제 정리 NxN 크기의 공간 M마리의 물고기 아기 상어 1마리 한 칸에는 물고기가 최대 1마리 존재(없거나 1마리) 초기 아기상어의 크기는 2 1초에 상하좌우 한 칸씩 이동 자신의 크기보다 큰 물고기가 있는 칸 제외 모든 칸 지나갈 수 있음 자기보다 작은 물고기 먹을 수 있음, 크기 같으면 지나만 갈 수 있음 이동 결정 알고리즘 더 이상 먹을 수 있는 물고기가 없으면 엄마에게 도움을 청함 먹을 수 있는 물고기가 1마리면 그 물고기를 먹으러 감 먹을 수 있는 물고기가 1마리 보다 많다면, 거리가 가장 가까운 물고기를 먹으러 감 거리: 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 ..
2020.10.22 -
BOJ 17144 미세먼지 안녕! 자바(java) 풀이 랭크 : 골드5 백준 17144 미세먼지 안녕! 문제 정리 집의 크기 RxC 공기 청정기는 항상 1번 열에 설치, 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있다. 1초 동안 다음고 같은 일이 일어난다. ㄱ. 미세먼지 확산. 미세먼지가 있는 모든 칸에서 동시에 일어남 네 방향으로 확산 공기청정기가 있거나 칸이 없으면 확산 X 확산 되는 양은 A(r,c) / 5 (소수점 버림) (r,c)에 남은 미세먼지의 양은 A(r,c) - ( A(r,c)/5 )x 확산된 방향의 개수 ㄴ. 공기 청정기 작동 위쪽 공기 청정기의 바람은 반시계 방향 순환, 아래쪽 공기청정기의 바람은 시계방향 순환 바람이 불면 미세먼지가 바람의 방향대로 모두 ..
[BOJ] 삼성 sw 역량 테스트 기출 :: 17144번 미세먼지 안녕! (java)BOJ 17144 미세먼지 안녕! 자바(java) 풀이 랭크 : 골드5 백준 17144 미세먼지 안녕! 문제 정리 집의 크기 RxC 공기 청정기는 항상 1번 열에 설치, 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있다. 1초 동안 다음고 같은 일이 일어난다. ㄱ. 미세먼지 확산. 미세먼지가 있는 모든 칸에서 동시에 일어남 네 방향으로 확산 공기청정기가 있거나 칸이 없으면 확산 X 확산 되는 양은 A(r,c) / 5 (소수점 버림) (r,c)에 남은 미세먼지의 양은 A(r,c) - ( A(r,c)/5 )x 확산된 방향의 개수 ㄴ. 공기 청정기 작동 위쪽 공기 청정기의 바람은 반시계 방향 순환, 아래쪽 공기청정기의 바람은 시계방향 순환 바람이 불면 미세먼지가 바람의 방향대로 모두 ..
2020.10.21 -
BOJ 17140번 이차원 배열과 연산 문제 자바(java) 풀이 랭크 : 골드4 백준 17140번 이차원 배열과 연산 문제 정리 크기가 3x3인 배열 A 1초마다 배열에 연산 적용 R연산: 배열 A의 모든 행에 대해서 정렬을 수행. 행 >= 열 C연산: 배열 A의 모든 열에 대해서 정렬을 수행. 행 < 열 각각의 수가 몇 번 나왔는지 알아야 함. 수의 등장 횟수가 커지는 순으로 정렬 그러한 것이 여러가지이면 수가 커지는 순으로 정렬 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저 R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변함 C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변함 행 또는 열의 크기가 커진 곳에는 0이 채워..
[BOJ] 삼성 sw 역량 테스트 :: 17140번 이차원 배열과 연산 (java)BOJ 17140번 이차원 배열과 연산 문제 자바(java) 풀이 랭크 : 골드4 백준 17140번 이차원 배열과 연산 문제 정리 크기가 3x3인 배열 A 1초마다 배열에 연산 적용 R연산: 배열 A의 모든 행에 대해서 정렬을 수행. 행 >= 열 C연산: 배열 A의 모든 열에 대해서 정렬을 수행. 행 < 열 각각의 수가 몇 번 나왔는지 알아야 함. 수의 등장 횟수가 커지는 순으로 정렬 그러한 것이 여러가지이면 수가 커지는 순으로 정렬 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저 R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변함 C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변함 행 또는 열의 크기가 커진 곳에는 0이 채워..
2020.10.19 -
BOJ 17779번 게리맨더링 2 문제 자바(java) 풀이 랭크 : 골드4 백준 17779번 게리맨더링 2 문제 정리 재현시의 크기 NxN 5개의 선거구로 나누어야 함 각 구역은 5개의 선거구 중 하나에 포함되어야 함 선거구는 적어도 구역 하나를 가져야 함 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함 인접한 구역을 통해 갈 수 있으면 연결되어 있다고 본다. 선거구에 있는 구역들은 모두 그 내에서 연결되어 있어야 한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자 문제 풀이 문제에서 주어진 대로 선거구를 정확히 나누기만 하면 쉬운 문제이다. 다만 처음에 0번 인덱스부터 했더니 헷갈려서 좀 걸렸다... 헤맸는데도 1시간 정도 걸린것 같다. 삼성 기출 중엔 쉬운..
[BOJ] 삼성 sw 역량 테스트 기출 :: 17779번 게리맨더링 2 (java)BOJ 17779번 게리맨더링 2 문제 자바(java) 풀이 랭크 : 골드4 백준 17779번 게리맨더링 2 문제 정리 재현시의 크기 NxN 5개의 선거구로 나누어야 함 각 구역은 5개의 선거구 중 하나에 포함되어야 함 선거구는 적어도 구역 하나를 가져야 함 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함 인접한 구역을 통해 갈 수 있으면 연결되어 있다고 본다. 선거구에 있는 구역들은 모두 그 내에서 연결되어 있어야 한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자 문제 풀이 문제에서 주어진 대로 선거구를 정확히 나누기만 하면 쉬운 문제이다. 다만 처음에 0번 인덱스부터 했더니 헷갈려서 좀 걸렸다... 헤맸는데도 1시간 정도 걸린것 같다. 삼성 기출 중엔 쉬운..
2020.10.18 -
BOJ 1021번 회전하는 큐 c++ 풀이 랭크 : 실버4 백준 1021번 회전하는 큐 문제 정리 N개의 원소를 포함하고 있는 양방향 순환 큐가 있다. 첫 번째 원소를 뽑아낸다. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라 문제 접근 arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다. 그래서 왼쪽으로 움직여서 id..
[deque, 덱] 백준 1021번 회전하는 큐 c++ 풀이BOJ 1021번 회전하는 큐 c++ 풀이 랭크 : 실버4 백준 1021번 회전하는 큐 문제 정리 N개의 원소를 포함하고 있는 양방향 순환 큐가 있다. 첫 번째 원소를 뽑아낸다. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라 문제 접근 arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다. 그래서 왼쪽으로 움직여서 id..
2020.07.03