Week_01 주차를 마치며 내가 일주일 동안 공부 해온 내용들을 글로 작성해보며 기록을 남기려고 한다.
week_01 주차에선 백준 문제를 풀며 자료구조와 알고리즘을 공부하면서 배우게 된다.
이번주 백준 문제 풀이 카테고리는 다음와 같이 명시되어 있다.
- 기초(입출력, 조건문, 배열, 함수, 문자열)
- 수학
- 재귀함수
- 정렬
- 완전 탐색
나는 개발 공부를 하면서 처음으로 알고리즘 공부를 해봐서 처음에 기초 문제를 보고 풀때에도 버벅거리고 문제들이 잘 이해가 안됐었다. 그래서, 뒤로 가면 갈수록 내가 지금까지 너무 얕은 지식으로만 공부 하고 그 지식에 대해 자기만족을 했던것 같아서 내 공부방법에 대해 다시 한번 돌아본것 같다. 지금껏 강의를 틀어 놓고 그대로 따라 쓰기만 하고 실제로 이 코드의 동작원리나 자세한 알고리즘은 무시한 체 넘어간것들이 많았던것 같아서 시간을 낭비 한것 같다고 많이 느껴졌다. 하지만, 이번 주차를 계기로 앞으로 매일 마다 꾸준히 시간을 들여서 알고리즘 공부를 더 해야겠다라는 생각이 들었고 더 많은 유형의 문제들을 접해야 겠다고 생각이 들었다.
다시 본론으로 돌아가서 기초로 돌아가보자
기초 문제를 각각 풀어보면서 이중에서도 정말 이해가 안가거나 어려웠던 문제들을 적어보면서 복습하는 시간을 가지려 한다.
1.기초
백준 2562번 (최댓값):
문제 출처: https://www.acmicpc.net/problem/2562
처음에 이 문제를 접했을때 최댓값을 Python의 내장함수인 Max() 를 써서 구하는것 까지는 알아차렸지만, 최댓값이 몇번째 수인지도 알아내라는 문장을 보고 처음엔 인덱스를 접근해야 겠다라는 생각이 먼저 들지 않았다.. (지금까지 인덱스 를 많이 사용했음에도 불구하고,,) 그래서 좀더 생각을 해볼 시간이 필요하다 느껴서 문제당 10분까지 고민해보고 이해가 안돼면 구글링 해보면서 문제를 이해하고 다시 문제를 풀어보니까 해결된 문제이다.
내 정답 코드)
nums = []
for i in range(9):
nums.append(int(input()))
max_num = max(nums)
max_idx = nums.index(max_num) + 1
print(max_num)
print(max_idx)알고리즘 문제들을 풀면서 항상 일반적인 접근 방식을 먼저 생각 해보고 적용 해봐야 한다는 생각이 들게 된 문제이다.
백준 8958 (OX 퀴즈):
문제 출처: https://www.acmicpc.net/problem/8958
OX 퀴즈 같은 경우는 인덱스로 접근 해야겠다라는 생각은 들었지만 인덱스 안에 있는 value값의 합을 어떻게 코드로 구현할까라는 생각이 드는 문제였다. 하지만, 생각을 아무리 해도 어떤 방법으로 구현해야 할지 아이디어가 떠오르지 않아서 결국 구글링을 통해 다음과 같은 접근법을 알게 됐다.
내 정답 코드)
T = int(input())
result = ''
for i in range(T):
list = input()
score = 0
sum = 0
for j in range(len(list)):
if list[j] == 'O':
score += 1
else:
score = 0
sum += score # score를 sum 이라는 변수에 다 합해서 저장 하고
result += (f'{sum}\n') # sum 값을 result 라는 변수에 저장 시켜
print(result) # result를 프린트 해준다.이 문제를 통해 인덱스를 이용해 인덱스 안의 value 값(즉, score)을 접근 하여 sum 이라는 변수에 value 값의 합을 저장하고 또 result 라는 변수명에 sum 값의 합을 저장하여 출력 해주었더니 문제가 풀렸다. 여기서 포인트는 인덱스의 value값을 먼저 접근 해봐야 한다는것이다. 해당 문제를 계기로 뒤에 나오는 문제들도 접근 법이 비슷해서 쉽게 풀어 나갈수 있었던것 같다.
백준 2908 (상수)
문제 출처: https://www.acmicpc.net/problem/2908
이 문제 같은 경우는 똑같이 인덱스 접근 방식으로 풀지만 기본적으로 우리는 숫자를 셀때 0부터 1씩 증가하는 숫자로 인덱스 가 증가 하는데 여기서는 그걸 반대로 생각 해서 풀어야 하는게 포인트 이다.
내 정답 코드)
a, b = input().split()
reverse_A = int(a[2]+a[1]+a[0])
reverse_B = int(b[2]+b[1]+b[0])
print(max(reverse_A, reverse_B))곰곰히 잘 생각 해보면 풀리는 문제들이지만 아직 까지는 뭔가 익숙치 않은것 같다라는 생각이 든다 더 많은 문제들을 접해 보면 나중에는 이런 문제들이 당연하게 생각 될꺼 라고 믿는다.
- 수학
백준 9020 (골드바흐의 추측):
문제 출처: https://www.acmicpc.net/problem/9020
이 문제 같은 경우 처음엔 문제가 잘 이해 되지 않아서 문제를 먼저 파악 하다보니 n 이라는 숫자가 주어지면 n를 절반으로 나눈후 나눠진 숫자가 각각 소수가 되면 출력 되게 만드는게 포인트다. 문제를 이해 하고 나니 조금씩 어떻게 접근해야 할지 감이 올랑 말랑 하는것 같다,, (그래도 여전히 알고리즘 문제 푸는건 어렵다...)
내 정답 코드)
def Goldbach():
check = [True] * 10000
# m = int(10000 ** 0.5)
for i in range(2, 101): #<=== #for i in range(2, m+1)
if check[i] == True:
for j in range(2*i, 10000, i):
check[j] = False
T = int(input())
for _ in range(T):
n = int(input())
A = n // 2
B = A
for _ in range(10000):
if check[A] and check[B]:
print(A, B)
break
A -= 1
B += 1
Goldbach()백준 1065 (한수):
문제 출처: https://www.acmicpc.net/problem/1065
이 문제는 등차수열에 대한 개념을 우선 알고 가야 한다.
등차 수열 이란? => 연속 하는 두 항의 차이가 모두 일정한 수열을 뜻한다.
ex) 1, 3, 5, 7, 9 는 등차수열이다.
다시 문제로 돌아가보면 어떤 양의 정수 x의 각 자리가 등차수열을 이루면, 그 수를 한수라고 한다.
결론을 보면 한수의 개수를 물어보는 문제이다.
내 정답 코드)
num = int(input())
hansu = 0
for i in range(1, num+1):
num_list = list(map(int, str(i)))
if i < 100:
hansu += 1 # 100보다 작으면 모두 한수
elif num_list[0]-num_list[1] == num_list[1]-num_list[2]:
hansu += 1 # x의 각 자리가 등차수열이면 한수
print(hansu)백준 2628 (종이 자르기):
문제 출처: https://www.acmicpc.net/problem/2628
이 문제 같은 경우 가로, 세로 값 과 자르는 횟수와 점선 번호를 지정 해주면 자른 종이 중의 가장 큰 종이의 넓이를 구하는 문제이다.
ex) 가로 10, 세로 8 , 자르는 횟수 3번, 점선 번호 (0,3), (1,4) (0,2) 이라고 했을때
가장 큰종이는 가로 5 세로 6 이 나온다. 이 종이의 넓이 값은 30이며 이 계산식을 코드로 짜보면 다음과 같다.
내 정답 코드)
r, c = map(int, input().split()) #자르는 위치 저장
row = [0, r] # [0, 10]
column = [0, c] # [0, 8]
for _ in range(int(input())): # 자르는 횟수
r_or_c, linenumber = map(int, input().split())
if r_or_c == 1: # 세로가 1 가로가 0-> 세로는 r에 가로는 c
row.append(linenumber)
else :
column.append(linenumber)
row.sort() # [0, 4, 10] # 빼서 최대 길이 구하기
column.sort() # [0, 2, 3, 8] # 빼서 최대 길이 구하기
temp = 0
for i in range(len(row)-1):
for j in range(len(column)-1):
area = (row[i+1]-row[i])*(column[j+1]-column[j])
if area > temp:
temp = area
print(temp)세로는 r 가로는 c 라고 생각 하고 문제를 접근 하면 나는 이해하기 좀더 쉬워지는것 같았다. 해당 문제를 그림으로 직접 잘라보고 수식을 써보면 그렇게 어려운 문제는 아니지만 인덱스를 활용해서 그걸 코드로 구현하려고 하니 어렵게 느껴졌다.. (인덱스 활용을 역시 잘해야 하는것 같다..)
- 재귀함수
백준 1914 (하노이 탑) :
문제 출처: https://www.acmicpc.net/problem/1914
이 문제 같은 경우 처음에 문제를 어떻게 접근 해야 재귀함수를 이용해서 해결 할수 있을까 고민하다... 도저히 모르겠어서 구글링을 통해서 반복되는 규칙성을 찾아내니까 푸는게 훨씬 수월해졌다. 이 문제의 포인트는 젤 기본적인 규칙성을 찾아내는것인데 그 규칙성은 다음과 같다:
ex) 장대가 3개 일때, 원판을 옮기는 위치를 좌표로 나타낼때 (1,3) => (1,2) => (3,2) => (1,3) 라는 규칙성이 생기게 된다. 이 규칙성을 알게 되면 코드를 짜기 쉬워진다.
내 정답 코드)
n = int(input())
def Hanoi(n, x, y):
if n == 1:
print(x, y)
return
Hanoi(n-1, x, 6-x-y)
print(x, y)
Hanoi(n-1, 6-x-y, y)
print(2 ** n - 1)
if n <= 20: Hanoi(n, 1, 3)x, y, n 으로 각 장대 마다 원판의 위치를 파악 할수 있는 코드를 짤수 있는데, n = 3 일때, x = 1, y = 3 이 되는데 그 이유는 장대1번 에서 장대 3번으로 원판을 옮겼기 때문에 좌표로 따지면 (x,y) = (1,3) 인것이다.
계속 해보면, Hanoi(2, 1, 2) 를 재귀로 호출 하게 되고 (x,y)좌표값을 출력 해준다, 그 다음엔 Hanoi(1, 3, 2) 를 재귀로 호출 하게 되어서 n == 1 이 되었을때, 해당 (x, y) 좌표 값을 프린트로 출력해준다. 이 순서를 계속 반복하게 되면 총 원판이 움직이는 횟수를 알수 있게 되는데 그 공식이 바로 2^n -1 이다. 그럼 n = 3 인 이 경우에는 원판을 옮긴 횟수가 7 이 되고 원판이 옮겨 질때 마다 재귀를 호출해 각 좌표값을 프린트 해주는게 이 문제 풀이 방법이다.
백준 9663 (N-Queen):
문제 출처: https://www.acmicpc.net/problem/9663
이 문제 같은 경우 n * n 크기의 체스보드 위에 n 개의 퀸을 놓았을때 서로 공격할 수 없게끔 하는 문제이다. 이 문제를 풀때 나는 무작정 퀸의 개수가 n개로 지정 되니 체스 보드 위에 퀸을 직접 놓아보면서 그림을 그려봤는데 경우의 수가 너무 많아서 이 방식으론 접근 하기 힘들어서 다른 방법을 고려 해보니 정말 간단한 방법이 있었다. 퀸은 보통 상하 좌우 대각선으로 자유자재 움직일수 있기 때문에 그걸 수식으로 나타내면 다음과 같다:
lst[a] == lst[i] or abs(lst[a]-lst[i]) == abs(a-i)
lst[a] == lst[i] 는 퀸의 위치가 상하좌우로 겹칠때를 나타내고
abs(lst[a]-lst[i]) == abs(a-i) 는 퀸의 위치가 대각선상에 겹칠때를 나타낸다.
이와 같이 이런 수식을 조건문 으로 써서 만약 이 조건문에 해당 된다면 해당 좌표에는 퀸을 놓을수 없게 된다. 즉, 서로 공격 할수 있는 자리에 못둔다는걸 의미한다. 이런경우의 ans 라는 변수에 경우의 수를 하나씩 추가하고 재귀호출을 여러번 해서 ans 를 프린트 출력 해준다.
내 정답 코드)
n = int(input())
lst = [0]*n
ans = 0
def queen(a):
global ans
if a == n:
ans += 1
return
else:
for i in range(n):
lst[a] = i
if check(a):
queen(a+1)
def check(a):
for i in range(a):
if lst[a] == lst[i] or abs(lst[a]-lst[i]) == abs(a-i):
return False
return True
queen(0)
print(ans)백준 1074 (Z):
문제 출처: https://www.acmicpc.net/problem/1074
이 문제는 처음에 재귀로 어떻게 접근해야할지 이해가 잘 안돼서 구글링을 통해 해결했다.
처음에 N, r, c 값을 받게 되면 r행 c열에 있는 값 을 출력 해주면 되는 간단한 문제이지만 이걸 재귀함수를 이용해서 코드를 짜려니 막막해서 가장 기본적인 접근 방법으로 생각 해보니 다음과 같은 규칙성? 을 발견 하게 됐다:
이 2차원 배열을 z 모양으로 탐색 하다 보면 1,2,3,4 사분면을 전부 방문 하면서 값을 찾게 되는데 N > 1 인 경우, 배열의 크기가 2^N-1 * 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문하게 된다.
이런식으로 처음 이차원 배열 에서 4배씩 증가하는 규칙성을 찾아볼수 있다.
만약 N, r, c 값을 3, 7, 7 을 받았다고 가정 해보자, 그렇게 되면 위 사진 처럼 배열이 4배 증가 되고 해당 사진에서 7행 7열에 있는 숫자를 찾아 프린트 해보면 출력값은 63 이 된다. 이와 같이 코드 로 구현해보면 아래의 코드와 같이 쓸수 있다:
내 정답 코드)
N, row, column = map(int, input().split())
def solve(N, row, column):
if N == 0:
return 0
return 2*(row%2)+(column%2) + 4*solve(N-1, int(row/2), int(column/2))
print(solve(N, row, column))4.정렬
백준 10989 (수 정렬하기 3):
문제 출처: https://www.acmicpc.net/problem/10989
이 문제는 정렬문제 중에서 좀 까다로웠던 문제중 하나 인데 그 이유는 바로 시간 복잡도 때문이다.
시간복잡도란? 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
시간복잡도 위키 백과: https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
빅오 표기법 과 시간 복잡도의 개념이해: https://blog.chulgil.me/algorithm/
내 정답 코드)
import sys
N = int(input())
check_list = [0] * 10001
for i in range(N):
input_num = int(sys.stdin.readline())
check_list[input_num] = check_list[input_num] + 1
for i in range(10001):
if check_list[i] != 0:
for j in range(check_list[i]):
print(i)해당 문제를 풀땐 정렬중 최악의 경우 O(n^2)이 나올수 있지만 해당 문제에서는 n<= 10000 이라서 O(10000*N)이 나오기 때문에 시간초과가 안나면서 정렬 할수 있다. 하지만 for 문을 돌리는것은 많이 추천하지 않는다 많이 돌리면 돌릴수록 시간복잡도는 커지기 때문이다.
백준 1181 (단어 정렬):
문제 출처: https://www.acmicpc.net/problem/1181
해당 문제는 sort 라는 파이썬 내장 함수를 이용해 풀어보았다. 코드는 비록 간단해 보여도 실제 sort함수가 실행 될때 마다 시간 복잡도는 O(NlogN) 이 나오기 때문에 해당 코드에서는 별 문제없이 돌아가는것이다. 문제를 풀어보면서 시간 복잡도의 개념과 중요성을 점차 깨닫게 되어 가는거 같다. 앞으로 문제를 풀때 좀 더 시간복잡도를 신경써보면서 풀어봐야 겟다.
내 정답 코드)
import sys
n = int(sys.stdin.readline())
dic = []
for i in range(n):
dic.append(sys.stdin.readline().strip())
set_dic = set(dic)
dic = list(set_dic)
dic.sort()
dic.sort(key = len)
for i in dic:
print(i)
- 완전 탐색
백준 10819 (차이를 최대로):
문제 출처: https://www.acmicpc.net/problem/10819
이 문제는 제목 그대로 한 배열이 주어지면 배열안에 각 정수 마다 앞뒤 의 차이를 최대로 뽑아내서 그걸 다 더하는게 포인트 인 문제이다. 예를 들어 [20, 1, 15, 8, 4, 10] 이라는 배열이 주어졌을때, 배열안에 있는 정수들의 순서를 적절히 섞어서 재 배열 한다 이때 각 정수의 앞뒤 차이를 최대로 하기 위해 생각 해보면 다음과 같은 배열이 나온다:
[8, 15, 1, 20, 4, 10] 해당 배열을 보면 각 정수의 앞뒤 차이가 각각 7, 14, 19, 16, 6 이 나오며 이를 다 더한값은 총 62 최대값이 나오게 된다. 자 그럼 코드를 살펴보자.
내 정답 코드)
n = int(input()) # 6
in_list = list(map(int ,input().split())) # [20, 1, 15, 8, 4, 10]
visited = [False]*n # [False, False, False, False, False, False]
answer = 0
def solve(new_list):
global answer
if len(new_list) == n:
total = 0
for i in range(n-1):
total += abs(new_list[i]- new_list[i+1])
answer = max(answer, total)
return
for i in range(n):
if not visited[i]:
visited[i] = True
new_list.append(in_list[i])
solve(new_list)
visited[i] = False
new_list.pop()
solve([])
print(answer)나는 해당 코드를 짤때, in_list, new_list, visited 라는 총 3개의 리스트를 만들었다.
여기서 in_list 는 처음에 우리가 받는 input 리스트를 의미한다.
new_list 는 우리가 in_list의 있는 값들을 재배열해서 넣는 새로운 리스트를 의미한다.
visited 는 True or False 로 in_list의 있는 값들을 완전탐색해서 비교 하여 앞뒤의 차이가 큰것들을 찾아 내는 일종의 check 리스트 이다.
해당 리스트들의 특성과 역할들을 잘 알고 있다면 이제 조건문과 반복문을 이용해 코드를 짜는건 어렵지 않다. 사실 여기까지 혼자서 도달하기는 너무 힘들었고 잘 풀리지 않아서 구글링을 해서 찾아본 결과 이다. 결국 이해 하면서 느끼게 된건 (컴퓨팅적 사고는 정말 어렵다...) 재미있다. 쉽게 접근 하기엔 어렵지만 찾아보면서 결국 이해하고 다시 복기 해보면서 내것으로 만들어 가는 과정이 재밌는것 같다.
백준 10971 (외판원 순회):
문제 출처: https://www.acmicpc.net/problem/10971
이 문제 같은 경우 포인트가 몇가지 존재한다. 그 포인트들은 아래와 같다:
- 아무 도시에서 출발 가능하다.
- 어떤 도시에서 방문한 도시까지 갈수 있으면 가본다.
- 방문한 도시들을 카운트 해준다.
- 만약 다른 도시로 갈수 없다면 리턴값을 최대로 지정해준다.
내 정답 코드)
import sys
def dfs(current, cost, cnt):
global min_cost
if cnt == N: #마지막에서 다시 처음으로 돌아가야함
if a[current][0]: #현재도시에서 처음 도시로
cost += a[current][0] #값을 더함
if min_cost > cost: #비교
min_cost = cost #미니멈이 순회비용보다 크면 순회비용이 미니멈이 됨
return #리턴
if cost > min_cost: #방문을 다 하기전에 값이 미니멈보다 크면 리턴 즉 다른 도시로 갈수 없다.
return
for i in range(N):
if not visited[i] and a[current][i]: #1-4, 이미 도시 0은 방문처리완료 현재 도시에서부터 i 도시
visited[i] = True #방문처리 완료
dfs(i, cost + a[current][i], cnt + 1) #재귀를 이용해서 시작도시, 다음도시, 벨류라는 변수에 저장, 방문도시 체크
visited[i] = False #도시 리셋
N = int(input()) #input 값을 받음 # 4
a = [list(map(int, input().split()))for _ in range(N)] #이차원적 리스트 를 생성 [[0,10,15,20],[5,0,9,10],[6,13,0,12],[8,8,9,0]]
min_cost = 1000000000 #변수 미니멈을 최대값으로 생성
visited = [False] * N #도시의 수만큼 False라는 인덱스 생성 [False, False, False, False]
visited[0] = True # 시작 도시는 무조건 True
dfs(0, 0, 1)
print(min_cost)해당 문제를 처음부터 접근 하기 너무 어려워서 구글링 하다가 찾아낸 방법 이다. 직접 코드를 보면서 느낀건 저런 포인트들을 잘 캐치 하고 보는 눈을 더 키워야 한다는게 참 쉽지 않은것 같다.. 하지만 포기 하지 않고 꾸준히 해내면 잘 될거라 믿는다.
백준 2468 (안전 영역):
문제 출처: https://www.acmicpc.net/problem/2468
이 문제 같은 경우 물에 잠기지 않는 안전한 안전영역의 최대 개수를 구하는 문제인데, 이 문제도 포인트가 몇가지 존재합니다. 포인트는 다음과 같습니다:
- 네방향을 돌면서 범위내에 안전영역인지 체크를 하는것
- 비가 만약 오지 않았을때
- 미방문 한곳을 어떻게 처리 해줄것인가
- 높이에 따라 안전한 영역인지 체크 하는것
내 정답 코드)
from collections import deque
def bfs(si, sj, h):
q = deque()
q.append((si,sj))
v[si][sj]=1
while q:
ci,cj = q.popleft()
# 네방향, 범위내, 미방문, 높이 > h
for di, dj in ((-1,0),(1,0),(0,-1),(0,1)):
ni,nj = ci+di, cj+dj
if 0<=ni<N and 0<=nj<N and v[ni][nj] == 0 and arr[ni][nj]>h:
q.append((ni,nj))
v[ni][nj]=1
def solve(h): # h높이에 대해 잠기지 않는 영역 개수 리턴
cnt = 0
for i in range(N):
for j in range(N):
if v[i][j]==0 and arr[i][j]>h:
bfs(i,j,h)
cnt += 1
return cnt
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for h in range(100): # 높이 0 ~ 99 까지 물 높이 지정
v = [[0]*N for _ in range(N)]
ans = max(ans, solve(h))
print(ans)이 문제도 마찬가지로 혼자 해결 하기 힘들고 접근 조차 힘들어서 구글링을 해보다 유튜브 강의를 듣고 한번 따라서 구현을 해보았다. 강의를 보면서 하니까 조금씩은 이해가 가지만 아직 완전히 이해 하고 넘어가려면 좀더 시간이 필요한것 같다,,
백준 안전영역 유튜브 강의: https://www.youtube.com/watch?v=7R5RlbjuI8U
