SWEA

[SWEA] 8458. 원점으로 집합 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 수학 풀이 한 번의 움직임을 쪼개서 진행할 수 있기 때문에, (ex. 2번째 움직임이라면 상으로 1칸, 우로 1칸) (3, 3)의 점과 (0, 6)의 점은 동일한 움직임 횟수가 필요하게 된다. 따라서 좌표의 x y 값이 아닌 좌표와 원점 사이의 거리 (abs(x) + abs(y)) 로 움직임을 계산한다. 모든 점이 원점에 모일 수 없는 경우 만약 (0,0)과 (0,1) 두 점이 있다면 두 점은 절대 원점에 모일 수 없다. 한 점이 원점에 있을 때 다른 점은 원점에서 거리가 1 떨어진 곳에 있기 때문이다. 즉, (0, a) 와 (0, b) 두 점이 있..

[SWEA] 2112. 보호 필름 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 구현, 완전탐색, 백트래킹 풀이 각 행은 약품 투입을 하지 않거나, A 약품을 투입하거나 B 약품을 투입하는 3가지 선택지가 있다. 경우의 수는 보호 필름의 두께(행의 수)는 최대 13이므로 3^13 = 약 160만 개이므로, 모든 경우의 수에 대해 완전 탐색하면서 유망하지 않은 경우는 가지 않는 백트래킹을 통해 시간을 단축한다. 유망하지 않은 경우는 현재 약품 투입 횟수가 지금까지 구한 약품 투입 횟수의 최솟값보다 크거나 같은 경우이다. 또 합격 기준이 K이면 연속된 K 줄에 같은 약품을 투입하면 무조건 검사에 통과할 수 있기 때문에 약품 투입 횟..

[SWEA] 5658. 보물상자 비밀번호 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 트리셋 풀이 N이 항상 4의 배수이므로 사각형의 한 변에 N / 4 개의 숫자가 적혀있다. 따라서 N / 4 번 회전하면 처음과 똑같아지므로 만들 수 있는 비밀번호의 수는 최대 (N / 4) * 4 = N 개이고, 이 중 중복을 제외한 K번째 수를 찾으면 된다. 각 비밀번호를 구할 때, 배열의 원소를 이동시키면 연산의 횟수가 많아지고 시간이 오래 걸리기 때문에 각 회전에서 각 변의 각 원소의 인덱스를 구해 비밀번호를 구한다. i번째 회전에서 j번째 변의 k번째 원소를 구하는 식은 다음과 같다. str.charAt((i + j * length + k)..

[SWEA] 4014. 활주로 건설 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 구현 풀이 백준의 14890. 경사로 문제와 동일한 문제로, 각 행과 열 중 조건에 맞는 행과 열의 개수를 세는 문제이다. 하나의 행과 열에 활주로를 건설할 수 있으려면 각 행과 열의 모든 원소가 다음 조건 중 하나를 만족하면 된다. 1. 현재 칸과 다음 칸의 높이가 동일한 경우 2. 현재 칸이 다음 칸보다 한 칸 높을 경우 && 다음 칸부터 + X 칸만큼 경사로를 놓을 수 있는 경우 3. 현재 칸이 다음 칸보다 한 칸 낮은 경우 && 현재 칸부터 - X 칸만큼 경사로를 놓을 수 있는 경우 경사로를 놓을 수 있는 조건은 다음과 같다. 1. 다음 칸(..

[SWEA] 5643. 키 순서 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 그래프, 플로이드 워셜(Floyd Warshall) 알고리즘 풀이 백준의 2458. 키 순서 문제와 동일한 문제로 해당 글과 풀이도 동일하다. 자신의 키가 몇 번째인지 알기 위해서는 자신보다 키가 작은 학생이 몇 명인지, 키가 큰 학생이 몇 명인지 알아야한다. 자신보다 키가 작은 학생은 그래프 상에서 [i][j]로, 자신보다 키가 큰 학생은 그래프 상에서 [j][i]로 표현될 수 있다. 예를 들어 예제 그림에서처럼 5번 학생이 4번 학생보다 키가 작다는 것을 graph[5][4] = true 로 표현한다면 6번 학생이 4번 학생보다 키가 크다 = 4..

[SWEA] 1263. 사람 네트워크 2 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 그래프, 플로이드 워셜(Floyd Warshall) 풀이 사용자 i의 다른 모든 사용자까지의 최단거리의 합을 CC(i) 라고 할 때, 모든 사용자의 CC 값 중 최솟값을 출력하는 문제이다. 따라서 플로이드 워셜 알고리즘을 이용해 모든 사용자로부터 다른 모든 사용자까지의 최단거리를 구하고 각 사용자마다 다른 모든 사용자까지 가는 최단 거리의 합(CC(i))을 구하고 최솟값을 갱신한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

[SWEA] 3307. 최장 증가 부분 수열 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 다이나믹 프로그래밍, 이분 탐색 풀이 LIS 문제이다. LIS 문제는 시간 복잡도 O(n^2)를 가지는 다이나믹 프로그래밍과 O(nlogn)을 가지는 이분 탐색 풀이법이 있다. 1. 다이나믹 프로그래밍 배열의 각 원소마다 자기보다 앞에 있으면서 크기가 작은 원소들 중 최장 증가 부분 수열의 길이가 가장 큰 값 + 1 이 자신의 최장 증가 부분 수열의 길이가 된다. 따라서 모든 원소를 탐색 후 dp에 저장된 최댓값이 해당 수열의 최장 증가 부분 수열이다. 2. 이분 탐색 최장 증가 부분 수열의 길이만을 구할 수 있는 방법이다. 최장 증가 부분 수열을 ..

[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 구현, 시뮬레이션, 백트래킹 풀이 1~W열까지 각 열에 구슬을 쏘는 경우라고 가정하여 구슬 쏘기를 진행하고, 해당 결과를 바탕으로 재귀를 돌려 1~W까지 N번 구슬을 쏘는 모든 경우를 탐색한다. 각 열마다 가장 위에 있는 벽돌의 index를 관리할 배열을 생성한다. 배열을 -1로 초기화해 벽돌이 없는 라인을 구분한다. 1~W열까지 각 열에 구슬을 쏘는 경우라고 가정하여 구슬을 쏜다. i열에 구슬 쏘기 1. 만약 i열에 벽돌이 없다면 구슬을 쏴도 의미가 없으므로 다음 열로 넘어간다. 2. i열에 벽돌이 있다면 맨 위의 벽돌을 깨고, 해당 벽돌의 정보(..

[SWEA] 1249. 보급로 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 너비우선탐색(BFS) 풀이 0,0 부터 N-1, N-1 까지 가는데 드는 최소 비용을 구하는 문제이다. 따라서 사방으로 너비우선탐색을 진행하며 마지막 칸에 도착했을 시 비용을 최솟값과 비교하고 갱신한다. 이때, 각 칸마다 가중치가 있기 때문에 boolean 형으로 방문 처리를 하게 되면 정답을 구할 수 없고, 방문 처리를 하지 않으면 무한 루프를 돌게 된다. 따라서 각 칸마다 해당 칸까지 이동하는 최소 비용을 저장하고, 최소 비용이 갱신되었을 때만 큐에 추가하는 식으로 방문 처리를 해준다. 코드 import java.io.BufferedReader;..