구해야 하는 것은 주어진 벽돌들 중 높이가 최대가 되도록 쌓을 때, 쓰인 벽돌의 개수와 각 벽돌의 순서 (단, 순서를 출력할 때에는 제일 위에 쌓인 벽돌의 순서부터 출력해야함)
벽돌을 쌓을 때의 규칙은 아래와 같음
벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
벽돌들의 높이는 같을 수도 있다.
탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다
문제 풀이
벽돌을 쌓을 수 있을지 없을지를 결정하는 요소가 '밑면의 넓이'와 '무게'이므로, 우선 둘 중에 하나를 기준으로 배열을 정렬해둠
정렬 이후 Dynamic Programming(동적 계획법)을 활용하여, 쌓을 수 있는지 없는지에 대한 판단을 요소별로 쪼개어 수행
Swift를 활용한 풀이
import Foundation
let n =Int(readLine()!)!// 벽돌의 개수var origin:[[Int]] = [] // 벽돌들의 정보// 벽돌 정보 입력 받기for_in0..<n {
origin.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
// 벽돌의 밑면의 넓이를 기준으로 내림차순 정렬var sorted_list = origin.sorted { $0[0] >$1[0] }
var dy:[Int] = [] // 높이합 최대 기록 배열var hist:[Int:[Int]] = [:] // 각 항목 별 쌓을 수 있는 벽돌의 무게 정보 - [s:[w1, w2, ...]]// 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)에 대한 정보는 기본적으로 저장 (비교 대상이 없기 때문)
dy.append(sorted_list[0][1])
hist[sorted_list[0][0]] = [sorted_list[0][2]]
// 최대값에 관한 정보는 모두 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)의 값으로 초기화// (0과 빈 배열로 초기화해두면, 0번째 값을 고려하는 경우가 없어지기 때문)var max_h_sum = dy[0] // 높이 합의 최대값var max_h_list:[Int] = hist[sorted_list[0][0]]!// 높이 합이 최대인 경우의 높이값 요소 배열// 2번째 벽돌 정보부터 살펴보면서, 이전 벽돌 중 자신이 위에 쌓일 수 있을지를 판단for i in1..<n {
var max_h =0var temp:[Int] = []
for j in (0..<i).reversed() {
// 이전 벽돌 중 자신보다 무게가 무거운 벽돌이면서, 높이의 합이 최대치인 경우의 정보를 임시 저장if (sorted_list[i][2] < sorted_list[j][2] && dy[j] > max_h) {
max_h = dy[j]
temp = hist[sorted_list[j][0]]!
}
}
// 바로 위 for문에 의해 결정된 '높이의 합이 최대이면서, 무게가 자기자신보다 무거운 벽돌'의 정보를 기반으로 dy와 hist 초기화
temp.append(sorted_list[i][2])
hist[sorted_list[i][0]] = temp
dy.append(max_h + sorted_list[i][1])
// dy와 hist의 정보가 추가될 때마다, 각 높이의 합과 그것을 이루는 높이 요소값 배열을 갱신if (max_h_sum < dy[i]) {
max_h_sum = dy[i]
max_h_list = hist[sorted_list[i][0]]!
}
}
// 결정된 최대 높이값의 요소 배열을 뒤집고 출력// (무게를 기준으로 내림차순 된 배열에서 값을 찾았기때문)
max_h_list = max_h_list.reversed()
print(max_h_list.count)
for w in max_h_list {
for i in0..<origin.count {
if(origin[i][2] == w) { print(i+1) }
}
}
상하좌우로 연속된 장애물 구역의 총 개수와 각 장애물 구역 내의 장애물 개수를 오름차순으로 출력
풀이법 구상
기본 DFS/BFS를 통한 탐색 문제
코드 구현 (자바 사용)
import java.io.*;
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args)throws IOException {
// 입력받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] map = newint[N][N];
for(int i=0; i<N; i++) {
char[] input = br.readLine().toCharArray();
for(int j=0; j<N; j++) map[i][j] = Character.getNumericValue(input[j]);
}
// BFS를 활용한 블록 탐색
ArrayList<Integer> block = new ArrayList<>();
boolean[][] ch = newboolean[N][N]; // 방문 여부 확인용(방문O - true / 방문X - false)
Queue<int[]> q = new LinkedList<>();
int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(map[i][j] == 1 && !ch[i][j]) {
int cnt = 1; // 장애물 개수
q.offer(newint[]{i,j});
ch[i][j] = true;
while(!q.isEmpty()) {
int[] cur = q.poll();
for(int d=0; d<4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 지도 범위를 벗어난 경우if(map[nx][ny] == 0) continue; // 도로인 경우if(map[nx][ny] == 1 && ch[nx][ny]) continue; // 이미 방문한 장애물일 경우
q.offer(newint[]{nx,ny});
ch[nx][ny] = true;
cnt++;
}
}
block.add(cnt);
}
}
}
// 결과 출력
Collections.sort(block);
System.out.println(block.size());
for(int b : block) System.out.println(b);
}
}
코드 구현 (파이썬 사용)
defdfs(x,y):if x<0or x>=n or y<0or y>=n: returnFalseif arr[x][y] == 1:
sum.append(1) # 연속된 구역 내 장애물 개수 +1
arr[x][y] = 0# 방문처리# 상하좌우 탐색
dfs(x,y+1)
dfs(x,y-1)
dfs(x-1,y)
dfs(x+1,y)
returnTruereturnFalse
n = int(input())
arr = []
for _ inrange(0,n): arr.append(list(map(int, input())))
sum = [] # 연속된 구역 내 장애물 개수를 추가할 배열
sum_arr = []
for p inrange(0,n):
for q inrange(0,n):
if dfs(p,q) == True:
sum_arr.append(len(sum)) # 연속된 하나의 구역을 탐색한 후, 구역 내 장애물 개수를 결과에 추가sum = [] # 새로운 연속된 구역 내 장애물 개수를 파악하기 위해 초기화
sum_arr.sort()
print(len(sum_arr))
for i inrange(0,len(sum_arr)): print(sum_arr[i])
- 같은 글자로 구성된 쌍은 사이에 'X'를 끼워주는데, 'XX'는 끼워줘봤자 여전히 중복이므로 'Q'를 끼워줌
- 가장 최종적으로 나온 쌍들 중 마지막이 1개 문자로 이루어졌다면 끝에 'X' 추가 (XX가 되어도 무관함)
각 쌍에 대해 입력받은 키값을 참고하여 다른 글자로 바꾸어줘야하는데, 참고할 키값은 길이와 상관없이 아래와 같은 규칙으로 5*5의 형태로 변형해야함
- 입력받은 키값을 차례로 돌면서 (0,0)자리부터 한 글자씩 채워줌
- 단, 이미 이전에 등장한 적이 있는 글자가 또 나오면 건너뜀
- 입력받은 키값을 이용해 채웠는데 25자리를 모두 채우지 못 한 경우, 알파벳 중 안 쓴 걸 가져다가 채우면 됨
풀이법 구상
문제가 아주 길어서 이해하는데 시간이 좀 걸렸음
문제를 풀어나갈 순서를 아래처럼 정리하면 크게 복잡한 논리를 요구하지는 않아보임
1. 메세지/키 입력받기 2. 2글자 쌍으로 나누기 3. 입력받은 키를 5*5의 형태로 변경 4. 쌍마다 암호화 (1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서 (2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서 (3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로
코드구현 (파이썬사용)
### 중복되는 글자쌍이 없도록 메세지 수정하는 메소드defgetPair(input):# 우선 2자씩 쪼개서 확인# 같은 글자로 구성된 쌍은 사이에 'X'를 끼워주는데, 글자쌍이 'XX'인 경우에는 'Q'추가# 가장 최종적으로 나온 쌍들 중 마지막이 1개 문자로 이루어졌다면 끝에 'X' 추가 (XX가 되어도 무관함)
result = inputwhile isDuplicated(result): result = setNotDuplicated(result) # 중복되는 쌍이 없을 때까지 반복iflen(result)%2 == 1: result += 'X'return result
### 중복되는 글자쌍이 존재하는지 확인하는 메소드defisDuplicated(str):for i inrange(0,len(str)-1,2):
ifstr[i] == str[i+1]: returnTruereturnFalse### 중복되는 글자쌍 사이에 'X' 혹은 'Q'를 추가하는 메소드defsetNotDuplicated(str):
str_list = list(str)
for i inrange(0,len(str)-1,2):
if str_list[i] == str_list[i+1]:
str_list.insert(i+1, 'X'if str_list[i] != 'X'else'Q')
return''.join(str_list)
### 입력된 키값을 기반으로 5*5 크기의 암호판을 만드는 메소드defgetKey(input_key):# 입력받은 키값을 차례로 돌면서 (0,0)자리부터 한 글자씩 채워줌# 단, 이미 이전에 등장한 적이 있는 글자가 또 나오면 건너뜀# 입력받은 키값을 이용해 채웠는데 25자리를 모두 채우지 못 한 경우, 알파벳 중 안 쓴 걸 가져다가 채우면 됨
alphabet_list = [chr(i) for i inrange(ord('A'),ord('Z')+1)]
alphabet_list.remove('J')
key_arr = []
# 우선 입력받은 키값으로 배열 채우기for k in input_key:
iflen(key_arr) == 25: breakif k in alphabet_list:
key_arr.append(k)
alphabet_list.remove(k)
# 배열 길이가 25 미만이면 안 쓴 알파벳 사용iflen(key_arr) < 25:
for a in alphabet_list:
iflen(key_arr) == 25: break
key_arr.append(a)
# 1차원 배열 값을 토대로 2차원 암호판 구성 후 반환# result_key = [[0] * 5] * 5 # 얕은 복사로 인해 값 변경에 오류 발생
result_key = [[0for p inrange(5)] for q inrange(5)]
for p inrange(0,5):
for q inrange(0,5): result_key[p][q] = key_arr[(5*p)+q]
return result_key
### 수정된 메세지의 글자쌍에 대해 키를 이용하여 암호화하는 메소드defgetResultMsg(pairs, key):# case 1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서# case 2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서# case 3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로
pair_arr = []
for i inrange(0,len(pairs)-1,2):
pair_arr.append(pairs[i]+pairs[i+1])
result = ''for pair in pair_arr:
result += getModifiedKey(pair, key)
print(result)
defgetModifiedKey(pair, key):
location = [
[-1, -1], # 첫번째 글자의 위치
[-1, -1] # 두번째 글자의 위치
]
for p inrange(0,5):
for q inrange(0,5):
if pair[0] == key[p][q]:
location[0][0] = p
location[0][1] = q
if pair[1] == key[p][q]:
location[1][0] = p
location[1][1] = q
if location[0][0] == location[1][0]:
# case 1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서
location[0][1] = (location[0][1] + 1)%5
location[1][1] = (location[1][1] + 1)%5elif location[0][1] == location[1][1]:
# case 2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서
location[0][0] = (location[0][0] + 1)%5
location[1][0] = (location[1][0] + 1)%5else:
# case 3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로
temp = location[0][1]
location[0][1] = location[1][1]
location[1][1] = temp
return (key[location[0][0]][location[0][1]] + key[location[1][0]][location[1][1]])
# 1. 메세지/키 입력받기
msg_input = input()
key_input = input()
# 2. 2글자 쌍으로 나누기
pairs = getPair(msg_input)
# 3. 입력받은 키를 5*5의 형태로 변경
key = getKey(key_input)
# 4. 쌍마다 암호화
getResultMsg(pairs, key)
파이썬을 사용하면 itertools 내 permutations 메소드를 써서 바로 풀이가 가능하지만 스위프트는 그런거 없음 왜..왜...
처음에는 1부터 n까지의 정수가 담긴 배열을 돌면서 하나씩 추가하고 배열에서 삭제해나가는 로직으로 생각했는데, 이러면 m중 반복문을 돌아야함 (그래도 시간복잡도가 O(N^m)이라 시간초과는 안 나겠지만 구현하기 까다로울 것 같아서 일단 포기)
1이상 n이하 정수 중에서 m개를 뽑는 방법은 DFS/BFS를 사용할 수 있는데
n이 4이고, m이 2인 경우를 생각해보면 1부터 4사이의 정수 중에 2개를 선택해야함
선택된 수를 담을 배열은 아래와 같은 경우의 수들을 가질 수 있음
[ ] -> [1] -> [1,2]
[ ] -> [1] -> [1,3]
[ ] -> [1] -> [1,4]
[ ] -> [2] -> [1,2]
[ ] -> [2] -> [2,3]
[ ] -> [2] -> [2,4]
...
[ ] -> [4] -> [3,4]
위 경우들은 트리로 시각화 할 수 있고, 각 노드들을 탐색하면서 노드를 구성하는 정수배열의 크기가 m인 경우만 중복없이 출력시키면 됨
는 그나마 익숙한 BFS로 구현했더니 시간초과
/// 시간초과난 코드import Foundation
funcsolution(_n: Int, _m: Int) -> Void {
var results: [[Int]] = []
for i in1...n { results.append([i]) }
// 수열 생성for_in0..<m {
for arr in results {
var temp: [[Int]] = []
for i in1...n {
if arr.contains(i) { continue }
var temp_arr = arr
temp_arr.append(i)
temp.append(temp_arr)
}
for t in temp {
if!results.contains(t) { results.append(t) }
}
}
}
// 사전 순으로 정렬var sorted_results: [[Int]] = []
for arr in results { if (arr.count == m) { sorted_results.append(arr) } }
sorted_results = sorted_results.sorted(by: { $0[0] <$1[0] })
// 정답 출력for arr in sorted_results {
var str =""for a in arr { str +="\(a) " }
print(str)
}
}
let input =readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)
구글링했더니 대부분 백트래킹으로 풀었음
백트래킹은 DFS와 비슷하지만 DFS는 종료 조건만 가지고 무지성 재귀함수를 사용하고, 백트래킹은 답이 있을 것 같은 경우에만 탐색하는 것이 차이점임
백트래킹에서 쓰이는 '유망함', '유망하지않음', '가지치기'의 용어도 정답 존재 가능성과 연관된 것임
- 유망함 : 정답을 찾을 수 있는 가능성 O
- 유망하지않음 : 정답을 찾을 가능성 X
- 가지치기 : 유망하지 않은 경우를 제외하는 것
(아무튼 다시 이 문제로 돌아와서) BFS 풀이는 배열의 수가 0개 -> 1개 -> 2개 -> ... -> m개인 순서로 노드들을 탐색하기 때문에, 배열의 길이가 0개부터 m-1개인 탐색할 필요가 없는 경우까지 고려하게 됨
그리고 모든 결과 배열을 다 포함하고 마지막에 탐색하면서 길이가 m인 배열을 사전순으로 출력하기 위해 따로 정렬도 해줘야 함
근데 백트래킹 풀이는 가장 적은 숫자부터 구성된 배열 중, 길이가 m인 경우에만 출력하게 하면 되니까 불필요한 경우의 고려와 정렬 코드가 삭제될 수 있음
그럼 백트래킹을 쓰려면 뭐가 유망한 거고, 뭐가 유망하지 않은 건지를 알아야 하는데 n = 4, m = 2인 경우를 예시로 보면,
결과배열이 [1]인 경우에는 1부터 4까지 중 1을 제외하고 추가해야함
이런 생각들로 아래처럼 구현하고 제출했더니 성공,,
코드구현 (스위프트사용)
import Foundation
funcsolution(_n: Int, _m: Int) -> Void {
let temp:[Int] = []
dfs(arr: temp, m: m, n: n)
}
funcdfs(arr: [Int], m: Int, n: Int) -> Void {
if (arr.count == m) {
var str =""for a in arr { str +="\(a) " }
print(str)
return
}
var temp = arr
for p in1...n {
if!temp.contains(p) {
temp.append(p) // 1부터 n 사이의 배열에 없는 숫자 중 젤 작은 거 추가
dfs(arr: temp, m: m, n: n) // 위에서 숫자 새로 추가한 배열로 다시 검사
temp.remove(at: temp.count-1) // 위에서 검사 끝나고 오면 가장 최근에 추가했던거 삭제(그 자리에 다른 새로운거 넣어보려고)
}
}
}
let input =readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)
DFS/BFS로 풀 수 있을 것 같아도 시간 복잡도 한 번 더 고려해보고, 뭔가 될 것 같아서 풀었는데 시간초과나면 백트래킹 풀이도 고려해보자
처음에는 이중 반복문을 돌면서 각 숫자를 음수로 바꾼 후의 총 합이 타겟과 같은지 판별하는 로직으로 구현했다가 실패
-> +4-1+2-1 과 같이 음수 사이에 양수가 존재하는 경우는 고려할 수 없음
각 숫자가 양수이거나 음수인 경우만 고려하면 되고 그러면 2^N의 시간 복잡도가 발생하는데, N의 최대값은 20으로 약 1,050,000이 됨
각 숫자가 양수이거나 음수가 되는 경우를 모두 고려하려면 각 숫자에 +,-를 붙인 노드로 이루어진 트리로 시각화할 수 있음
각 노드를 탐색하며 더한 합계값을 타겟 넘버와 비교하면 결과값 도출 가능
탐색에는 BFS/DFS를 모두 사용할 수 있으나 제출 코드는 BFS사용
코드구현 (스위프트사용)
import Foundation
funcsolution(_numbers:[Int], _target:Int) -> Int {
var result =0var sum_arr = [0] // 반복문 시작을 위해 0 하나 추가for n in numbers {
var temp: [Int] = []
for s in sum_arr {
temp.append(s+n)
temp.append(s-n)
}
sum_arr = temp
}
for s in sum_arr { result += (s == target) ?1 : 0 }
return result
}
n명에게 각각 예상 등수값을 입력받고, 그 값들을 토대로 불만족 지수가 최소로 나오도록 구성하여 불만족 지수의 최소값을 출력
불만족 지수란 예상 등수가 1등이고, 실제 순위 구성 후 등수가 3등인 경우 (|1-3|)으로 2의 값이 됨
(n의 범위는 1이상 500,000이하)
풀이법 구상
예상 순위보다 실제 순위가 높든 낮든 무관하게 그 차이값만큼이 불만족 수치가 됨
최대한 예상 순위가 실제 순위가 되도록 해야하므로 정렬 후 각 예상 순위값을 돌며 실제 순위와의 차이값을 구해야함
정렬 + 반복문이 필요함
-> 스위프트 기본 정렬 메소드의 시간복잡도 - O(n log n)
-> 반복문 시간 복잡도 - O(N)
-> 동시에 일어나지 않고 정렬 후 반복문 돌게됨
코드구현 (스위프트사용)
import Foundation
funcsolution(_arr: [Int]) -> Void {
var sum =0let temp = arr.sorted()
for i in1...arr.count { sum +=abs(i - temp[i-1]) }
print(sum)
}
var arr: [Int] = []
let cnt =Int(readLine()!)!for_in0..<cnt { arr.append(Int(readLine()!)!) }
solution(arr)
