YoungSoo

이 색종이 만들기 문제는 백준에서는 분할 정복 알고리즘으로 분류되어 있다. 여기서 분할 정복 알고리즘은 기본적으로 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 푸는 문제인데 재귀 함수랑 비슷하다고 생각이 들어 재귀함수처럼 함수 내에서 자기 자신의 함수를 호출하여 푸는 방식으로 알고리즘을 생각해보았다. 풀이 import sys input = sys.stdin.readline n = int(input()) bd = [list(map(int, input().split())) for _ in range(n)] result = [] def d(x, y, n): color = bd[x][y] for i in range(x, x+n): for j in range(y, y+n): if color != bd[i][j]..

누적합 알고리즘 - 매우 많은 수를 반복할 수도 있기에 시간복잡도를 줄이는 알고리즘을 짜야하는데 그 알고리즘은 대체적으로 미리 배열에 수를 저장한 뒤 계산을 통해 값을 도출해내야하며 이것을 통해 수가 큰 답에서도 시간을 단축할 수 있다 이번 문제는 누적합 알고리즘을 통해 문제를 해결할 수 있는 문제였다. 앞에 푼 구간 합 구하기 4문제랑 유사하지만 이번 문제는 1차원 배열에서 구하는 것이 아닌 2차원 배열 공간에서 구하는 것이다. 그렇기 때문에 약간 다른 점이 있었다. 예를 들어 (x1=2, y1=2), (x2=3, y2=4) 이와 같은 예제가 있을 때 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 빨간색 숫자를 제외한 나머지는 제외하고 구해야하는데 그냥 누적합만 한다면 파란색 숫자는 제외하고..

백트래킹에서의 마지막 문제였는데 백트래킹 알고리즘은 정말 어려웠다. 먼저 틀린 예제를 보자. import sys input = sys.stdin.readline def dfs(a): global result if len(s) == n//2: lt, st = 0, 0 for i in range(1, n+1): for j in range(1, n+1): if i not in s and j not in s: lt += arr[i-1][j-1] elif i in s and j in s: st += arr[i-1][j-1] result= min(result, abs(lt-st)) return for i in range(a, n+1): if i not in s: s.append(i) dfs(i) s.pop() n=..

이 문제를 처음 풀었을 땐 factorial함수와 반복문을 이용해서 구하였는데 이 방식으로 구하면 시간초과로 인해 실패한다. 그 이유는 2,000,000,000이라는 큰 숫자까지 풀 수 있기 때문에 반복문을 사용하면 시간초과가 나올 수 밖에 없었다. 그래서 새로운 방법을 생각했는데 그 방법은 끝자리가 0일 때는 10의 배수이며 10은 2와 5로 구성되어 있다. 2와 5의 개수가 같아야 10의 배수가 되므로 2와 5중에 작은 것의 개수를 구한다면 답이 나올 수 있다. import sys input = sys.stdin.readline def cnt(a,b) : result = 0 while a != 0: a = a//b result+=a return result n, m = map(int, input()...

이번에는 예외처리에 대해 공부하려고 한다. 예외처리는 프로그램을 만들다보면 많은 오류가 발생하는데 오류로 인해 프로그램이 잘못 작동하는 것을 막기 위해 해준다. 예외처리 try, except문 try: ... except [발생 오류[as 오류 메시지 변수]]: ... // 0으로 값을 못 나눔. try: 4 / 0 except ZeroDivisionError as e: print(e) >> division by zero try .. finally f = open('foo.txt', 'w') try: # 무언가를 수행한다. finally: f.close() try문에 else 절 사용하기 try: ... except [발생 오류[as 오류 메시지 변수]]: ... else: # 오류가 없을 경우에만 수행..

코딩테스트를 공부하다가 최대공약수 혹은 공약수 최소 공배수를 구하는 문제를 많이 접하게 되어 유클리드 호제법을 꼭 알고 가야겠다라는 생각이 들었다 유클리드 호제법이란, 숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수와 같다는 것을 의미한다. 따라서 최대 공약수를 구하는 코드는 이렇게 된다. 최대공약수 def gcd(a, b): while b > 0: a, b = b, a % b return a 최소 공부새는 a, b의 곱을 최대 공약수로 나누면 알 수 있다. 최소공배수 def lcm(a, b): return a * b / gcd(a, b) 공약수 공약수는 최대 공약수의 약수를 구하면 된다. 따라서 약수를 구하는 법을 알아보려고 한다. 약수를 구하는 방법은 몇..

이번에는 파이썬의 패키지에 대해 공부해보려고 한다. 패키지는 .을 사용하여 파이썬 모듈을 계층적으로 관리할 수 있도록 해준다. 패키지 디렉터리와 파이썬 모듈로 이루어진다. game/ __init__.py sound/ __init__.py echo.py wav.py graphic/ __init__.py screen.py render.py play/ __init__.py run.py test.py .py는 파이썬 모듈이고 game 디렉터리는 루트 디렉터리이며 sound, graphic, play는 서브 디렉터리다. 패키지 안의 함수 실행하기 //1 import game.sound.echo game.sound.echo.echo_test() >> echo //2 from game.sound import echo..

이번 문제는 참외밭의 크기를 구하는 문제인데 배열에 이동하는 거리를 하나씩 대입하여 가장 긴 가로 변의 인덱스의 +1, -21 그리고 가장 긴 세로 변의 인덱스의 +1, -1을 해서 풀었는데 이 방식에서 예외처리를 해주지 않아 오류가 났다. import sys input = sys.stdin.readline k=int(input()) arr = [] for i in range(6): x, y = map(int, input().split()) arr.append(y) mw = max(arr) mh = arr[arr.index(mw)-1] if arr[arr.index(mw)-1] > arr[arr.index(mw)+1] else arr[arr.index(mw)+1] nw = abs(arr[arr.index..