https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.
34번 (10819) 차이를 최대로
해당 문제는 N개의 정수로 이루어진 배열에 대해 앞의 수와 바로 뒷 수의 차가 제일 커야한다. 문제 이해도 잘안됐고, 코드 작성에 어려움이 있어 GPT와 블로그들의 도움을 받아 클론 코딩하며 이해했다.
from itertools import permutations # itertools라는 라이브러리의 permutations 순열함수를 임포트해서 쓴다.
# 주어진 배열 arr에 대해 |A[i] - A[i+1]|의 합을 계산하는 함수이다.
def difference_sum(arr):
total = 0 # 합을 저장할 변수의 초깃값을 0으로 한다.
for i in range(len(arr) - 1): # 전체 배열길이의 -1 만큼 반복(왜냐하면 조합이 N-1만큼 반복되므로)
total += abs(arr[i] - arr[i + 1]) # 배열의 현재 인자와 다음 인자를 뺀걸 더한다.
return total # 계산된 총 값을 돌려준다.
# 위에서 보낸 합을 토대로 차이의 합의 최대를 구하는 함수이다.
def difference_max(n, arr): # 입력된 N만큼 반복한다.
max_value = 0 # 최대 합을 저장할 변수의 초깃값을 0으로 한다.
# 모두 가능한 순열을 생성하여 검사(매칭될 수 있는 모든 경우의 수를 고려한다고 생각하자)
for perm in permutations(arr): # permutations(반복가능한 객체, r)로 중복을 허용하지 않고 r개를 뽑아 나열한다. 그러나 뽑힌 순서는 생각한다.
max_value = max(max_value, difference_sum(perm)) # 조합이 최대가 될때까지 최댓값을 갱신한다.
# 현재의 합이랑 이후 계산한 새로 매칭된 조합의 합을 비교해서 더 큰것을 뽑기 위해 해당 코드를 쓴다.
return max_value # 최댓값을 반환한다. 들여쓰기 주의!
# 입력 처리
n = int(input()) # 첫번째줄의 배열의 갯수를 받는다.
arr = list(map(int, input().split())) # 두번째줄의 배열 값을 받는다.
# 결과 출력
print(difference_max(n, arr)) # 최댓값을 프린트한다.주석을 하나 하나 달고, 새로 임포트 하는 라이브러리인 itertools와 permutations함수에 대해 알아 보았다. permutations 라는 함수가 가능한 모든 수열을 생성한다는 것이 굉장히 편리한 것 같다. 코드에 주석을 달며 이해하긴 했으나 작성은 어려움을 느껴 다시 복습해야할 것 같다.
15:30 ~ 16:00
백승현 코치님의 알고리즘 기초
해당 시간에 백승현 코치님이 알고리즘 기초에 관해 짧게 강연하셨다. 내용을 대충 정리해보겠다.
프로그램 = 알고리즘 + 자료구조
알고리즘은 연습하면 는다. 그러니 노력하자. 코치님도 초반엔 잘 못하셨다고 하신다.
맨첨엔 팩토리얼을 설명하셨다. 꼭 재귀함수에 대해 이해하고, 점화식을 일반화하는 방법을 생각해보라고 하셨다. 피보나치 코드도 구현하고… 재귀함수와 점화식을 대비해서 이해할수 있어야한다고 하셨다.
나중에 나올 이진트리(정처산기에서 나옴)의 전위, 중위, 후위를 알고리즘으로 구현해보라고 하셨다. 특히, 후위
반복문으로 구현은 어려운데 재귀는 금방 처리가능하다고 한다.
그럼 어떤 문제에서 점화식을 사용할지 확인을 하는가?
→ 연습많이하는게 중요하다. 그러나 n에 작은 값인 3을 넣어보는 방법도 있다고 하셨다, 규칙을 알 수 있으니
합병 정렬 n일 때 n/2 특징을 파악하고 n을 푼다고 하신다. 문제를 반으로 쪼갠 것과 같으니까.
정렬 알고리즘에서 시간복잡도와 공간복잡도에 대해 설명하셨는데, 요즘 컴퓨터 성능이 좋아 공간복잡도는 상관안한다고 한다. 시간복잡도가 굉장히 중요한데, 컴퓨터 연상의 가능/불가능을 가늠하기 때문이다.
시간복잡도O(n) = n^2, n^3, 2^n, n!등 다양하다.
이를 예시를 들기위해 회전판 순환을 예시로 드셨다.
이후 정렬방식을 설명하셨다.
| 정렬타입 | 시간복잡도 | 안정도 | 평균 |
|---|---|---|---|
| 삽입 | O(n^2) | stable | O(n^2) |
| 합정렬 | O(nlogn) | unstable | |
| 합병 | O(nlogn) | stable | |
| 퀵 | O(n^2) | unstable | O(nlogn) |
여기서 나중에 알아볼 과제를 주셨는데 여기서 퀵소트방식이 제일 많이쓴다.
위에서 보면 알듯이 제일 느리고 불안정적인데 왜 쓰는지 알아보라고 하셨다.
→ 찾아봤다. 퀵 정렬의 루프는 대부분 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있습니다. 메모리 참조가 지역화되어 있어 CPU 캐시의 히트율이 높아지기 때문입니다.
알고리즘을 어떻게 짜는가? → 알고리즘은 개념적으로 알고 있으면 코드를 적을 수 있을것이라 하셨다.
시간 초과시 어떻게 해결하는가? → 여러가지 시도를 해보자.
알고리즘 공부할때 시간이 너무 걸리는데 어떻게하죠? → 알고리즘 공부시 시간을 오래 쓰지 말고 답을 보고 이해하자. 어느정도 실력이 되면 길게 생각해보는 것이 좋다.
알고리즘에 대해 다양한 것을 알게되었다.
35번 (10971) 외판원 순회 2
해당 문제는 내용이 좀 길고, 알고리즘 문제로 유명하다. 고로 문제를 스크랩해왔다. 이해가 안되면 링크를 들어가 보자 https://www.acmicpc.net/problem/10971
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자. N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하세요.
입력은 다음과 같다.
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다.
문제를 읽고 내가 이해한 것은 여행 경로를 짜야하는데, 한 출발점에서 시작하여 N개의 여행지를 거치고 다시 출발점으로 와야된다. 갔던 여행지는 다시 갈 수 없고 수 많은 경로에서 제일 최단 경로를 짜는 것이 이 문제의 핵심이다. 그러나 어떻게 코드로 풀어나갈지 가늠이 되지 않는다. 모든 경로를 입력해서 최적의 경로가 나올때까지 돌리는 방법일 것 같은데...
일단 아무 경로를 돌린다. 최소비용이 나오면 함수에 입력한다. 다음 방법으로 넘어간다. 만약, 더 적은 비용이 나온다면 갱신한다. 근데, 합을 진행하다가 현재 있는 최소비용보다 커질수 있다.(결과가 나오기도 전에) 그러면 더이상 진행하지 않고 되돌아간다.(백트래킹) 개인적인 느낌은 무대뽀로 모든 수를 넣어보고 최솟값을 구하는데, 어느정도 최적화를 해야하니 백트래킹을 통해 어느 조건(여기선 현재까지 구한 최솟값)보다 크면 중단하고 되돌아가서 경로를 재탐색하는 것이다.
일단은 구현해보겠다.
import sys
def backtracking(path, cost):
global min_cost
# 모든 도시를 방문했을 경우
if len(path) == N:
start = path[0] # 출발도시
last_city = path[-1] # 마지막 방문 도시(-1을 쓴 이유는 리스트의 마지막 요소를 가져오기 위해서)
if W[last_city][start] > 0: # 출발지로 돌아갈 수 있는 경우(출발지로 돌아간다는 조건에 맞는 경우)
# 여기서 W[i][j]은 비용 행렬로 도시 i에서 j로 가는 비용으로 이해하면 된다.
# W[i][j] = 0 이면 이동할 수 없고 W[i][j] > 0은 이동할 수 있다는 뜻이다.
min_cost = min(min_cost, cost + W[last_city][start]) # 위의 값과 기존값과 비교해 최솟값으로 최소 비용 갱신
return # 결과를 돌려준다.
# 백트래킹요소: 현재 비용이 최소 비용보다 크면 종료시키고 다른 경우를 찾는다.
if cost >= min_cost:
return
# 밑의 코드는 도시의 거리를 지나가는 경우와 되돌아 오는 것을 제외하는 코드를 작성해야할 것 같다.
# 다음 방문할 도시를 찾는다.
for next_city in range(N):
if next_city not in path and W[path[-1]][next_city] > 0:
# 해당부분이 어려울수 있는데, 영어 시험본다 생각하자 not in path(방문하지 않았고)이고
# W[path[-1]][next_city] > 0 는 이동가능하다는 뜻이다.
path.append(next_city) # 경로에 추가
backtracking(path, cost + W[path[-2]][next_city]) # 재귀를 호출한다.
# 이전 방문 도시를 의미하며, 현재 방문한 도시에서 다음 도시로 가는 비용을 더합니다.
# 바로 윗줄에서 추가된 next_city가 현재 path[-1]이고 해당 도시 전에 추가된 것이 path[-2]이다
path.pop() # 백트래킹 (원래 상태 복귀), 있었던 도시(인자)를 뺍니다
# 입력 처리
N = int(input()) # 도시수
W = [list(map(int, input().split())) for _ in range(N)] # 비용 행렬
# N에 입력된 도시수만큼 도시별 비용을 입력 받겠다는 뜻이다.
min_cost = sys.maxsize # 최소 비용을 초기화한다.
# 만약에 해당 문구가 없다면 위의 min(min_cost, cost + W[last_city][start])에서 비교 대상이 없어 오류가 나온다.
# 그렇다고 min_cost = 0 을 하면 전 문제와 다르게 작은값을 구하므로 항상 답이 0이 나오는 경우가 발생된다.
# 시작은 모든 도시에서 가능
for start in range(N):
backtracking([start], 0) # 시작 도시만 포함한 경로로 시작
print(min_cost) # 최소 비용 출력해당 문제도 어렵다... GPT와 블로그들의 도움을 많이 받았다. 클론코딩 형식으로 풀었다. 솔직히 이해하는데 시간이 너무 오래 걸렸다. 아직까지도 입력된 여러 도시에서 최소비용을 구해야되서 백트래킹을 사용해야된다는건 알겠는데 왜 이렇게 나오는지는 2차원배열이 익숙치 않아서 그런것 같아 공부를 더해봐야겠다.
다른 문제를 위해 여기까지 하고 다음 문제로 넘어가겠다. 미련이 남아서 공부했는데, 해당 문제는 그림을 그려보니 단번에 이해가 갔다. 입력값이 2차원 배열로 되어 있어서 이해가 안되는 것이었다. 만약 다음에도 이해가 안된다면, 인풋값을 인자로 두고 표를 그려보자.
DFS와 백트래킹에 대한 궁금증
- 해당 문제의 백트래킹 공부하다가 생각이 든게 있다. 백트래킹이 모든 경우의 수를 고려하다가 이미 나온 결과보다 조건이 맞지 않으면 중단하고 다른 수를 탐색한다. 그러면 계속해서 끝까지 가는 DFS보다 항상 좋은 방법이 아닌가? 라는 생각이다.
→ 해당 궁금증을 해소하기위해 동료분과 GPT의 도움을 받았다.
보통은 백트래킹을 쓰는 것이 좋다 하지만, 미로를 예시로 들어 설명을 해보겠다.
미로의 출구만. 찾는 다면 당연히 백트레킹으로 막다른 길 아닌것 제치고 맞는 길로만 확인해서 경로를 뽑는 것이 맞다. 근데, 미로의 출구의 존재 여부, 즉 모든 경우의 수를 확인해야된다면 DFS를 써야된다. 제한되는 조건도 없고 모든 경우의 수를 알아야하니까.
개인적인 생각으론 조건이 있다? → 백트래킹
조건이 없고 모든 경우를 봐야한다? → DFS 를 선택하는 편이 좋다고 생각한다. - 백트래킹이라면 프로그램 돌릴 때마다 결과 나오는 시간이 다른가?
확인해보니 시간은 같다고 하다. 값을 입력하는 순서는 변하지 않기 때문이다.(랜덤 돌리지 않은 이상)
28번 (1074) Z
못풀었던 문제로 돌아왔다.
해당문제는 직접 보는게 빠르다. https://www.acmicpc.net/problem/1074
문제 이해는 쉽다. 그런데 코드 구현을 어떻게 해야할지 모르겠다. 2^N으로 증가하면서 저 Z 모양이 반복된다. 근데 이게 Z의 다음 위치도 큰 Z자로 지나간다. 다른 내용을 참고 했는데, 해당 문제는 재귀와 분할 정복으로 풀 수 있다고 한다. z를 반복적으로 불러오는건 재귀로 하면되고 해당 규칙이 2^n만큼 반복되니, 재귀 분할해서 처리하고 나중에 합치는 느낌이다. 일단 재귀 연습이라고 할 수 있게끔 재귀처리전 코드라도 가져왔다.
# def Z(N,r,c):
# ans = 0
# while N:
# N -= 1
# if r < 2**N and c < 2**N:
# ans = ans
# elif r < 2**N and c >= 2**N:
# ans += 2**(2*N)
# c -= 2**N
# elif r >= 2**N and c < 2**N:
# ans += 2*(2**(2*N))
# r -= 2**N
# elif r >= 2**N and c >= 2**N:
# ans += 3*(2**(2*N))
# r -= 2**N
# c -= 2**N
# return ans
# 해당공식을 내 힘으로 재귀형태로 바꿔볼려 했으나 실패했다. 시간도 부족해서...
def sol(N,r,c): # 입력받은 인자가 수행하는 함수
if N == 0: # 기초적 상황인 N이 0인 경우에는 0을 반환하도록한다.
return 0
# Z 순서 계산
else:
return 2*(r%2)+(c%2) + 4*(sol(N-1, r//2, c//2))
# (r%2)와 (c%2)로 나머지를 뽑아서 현재 블록에서의 상대 위치를 구한다. (N=1 기준 0~3 사이의 값)
# 해당 식에 2를 곱하는 이유는 이렇게 해야 행과 열에 따라 좌우상단, 좌우하단을 0~3으로 구현가능하다.
# 2 안 곱하면 좌표값 0,1 이런식이라 0,1,2 이렇게 나온다.
# 4배씩 증가하는 패턴을 고려하여 4 * sol(N-1, r//2, c//2) 를 추가한다
# (N-1, r//2, c//2)에서 N-1은 블럭을 전단계로 나눴기 때문에 현재 단계 전 단계 결과를 불러오기 위함이다.
# r//2, c//2의 //는 몫을 구하는 것으로 하위 블록에서의 위치이다.
# 이후 4를 곱하면서 현재 우리가 존재하는 블록으로 복구시킨다.
# N을 N-1로 축소화 시킨다음 다시 키운다고 생각하면 된다.
# 근데 그 안에서의 위치를 우린 모른다. 그러니까 2*(r%2)+(c%2)을 더해서 안에서의 위치 값을 추가한다.
N,r,c = map(int, input().split()) # 입력값 받기
print(sol(N,r,c))엄청나게 긴 함수를 한줄로 줄인게 대단하다. 어떻게 이렇게 하는지... 이거 한줄로 만든사람은 노벨상 받아야되는거 아닌가 싶을 정도다. 한줄을 분해하고 이해하는데 한세월 걸렸다.
이제 마지막 문제인 안전영역을 풀려 했으나 시간이 늦어 추후에 풀어보겠다.
일상
세탁실에서 세탁하다가 정글 면접 같이 보신분을 만났다. 전공은 항공소프트웨어공학과셨다. 반가워서 정글까지 온 계기와 느끼고 있는것, 알고리즘이 어렵더라 등 다양한 이야기를 나눴다. 혹시 모르니 연락처도 교환하고 담에 다시 보자고 기약하고 헤어졌다. 같이 면접 본 분을 만나게 되니 신기했다. 각자 살아간 얘기를 들어보니 그것보다 값지다고 생각하며 간접 경험을 하는 정글에 대해 굉장히 좋은 프로그램이라고 생각한다.
