백준

[백준 24313] 점근적 표기 1 문제 풀이 & 해설 - 파이썬

백준 24313 문제에 대해 풀어보겠습니다. 이 문제는 알고리즘 수행 시간에 관한 문제로 "점근적 표기 (asymptotic notation)"에 관해 알고 있는지를 묻고 있습니다. Background: 점근적 표기 점근적 표기에 대해 간략히 설명을 하자면, Big-O를 계산할 때 입력값의 크기에 따라 함수가 얼마나 빨리 커지는지 알아볼 때 중요하지 않은 항과 상수 계수를 제거하면서 이해를 방해하는 불필요한 부분을 없앤 표기법이라고 볼 수 있습니다. 즉, 간략한 예로 $ y = 0.0006n^3 - 1000 $라고 했을 때, $O(y)=n^3$ 가 되는 반면에, $ x = 1000n^2 + 1000 $의 Big O는 $O(x)=n^2$ 가 되기 마련입니다. 따라서 y의 수행시간이 x보다 더 크다고 할 수..

[백준 9506] 약수 합 - 파이썬

백준 9506번 문제는 약수들의 합을 구해 완전수 (perfect number)인지 아닌지를 판별하는 문제입니다. 저는 다음과 같이 풀었습니다. while 문으로 exit (-1)전까지 입력을 받습니다. 1부터 n까지 for문을 돌면서, 나머지가 없는 즉, 모든 약수 (factor)를 리스트에 기록합니다. 약수의 합이 입력 값(n)과 같은지 확인하고 맞다면 형식에 맞춰 출력을 진행 if __name__ == '__main__': while True: n = int(input()) result = [] if n == -1: break else: for i in range(1, n): if n % i == 0: result.append(i) if n == sum(result): result = list(ma..

[백준 11005] 진법 변환 2 - 파이썬

백준 11005번은 '주어진 10진법 수 N을 사용자가 지정한 진법 B로 변환하는 알고리즘'을 만드는 문제입니다. 원리만 이해하면 생각보다 간단하게 풀 수 있습니다. 간단한 예시를 통해 이해하고 답을 보겠습니다. 예시 10진수 10을 2진수로 변환하는 경우: N = 10, B = 2 10진수 -> B진법 변환은 나머지를 기록해둘 필요가 있습니다. 또한 10진수 값 N 을 B로 나눴을 때 몫을 기억해둘 필요가 있습니다. 지속적으로 업데이트 해주어야 합니다. 10 % 2 = 0 --> 나머지 = "0" N // B : 10 // 2 = 5 --> 몫 = "5" N = 5 (i.e. N = N // B) 5 % 2 = 1 --> 나머지 = "1" N // B: 5 // 2 = 2 --> 몫 = "2" 2 % ..

[백준 2563번] 색종이 - 파이썬

백준 2d array 부분 색종이 알고리즘에 대해 풀어보겠습니다. (https://www.acmicpc.net/problem/2563) 처음 이 문제를 접했을 때 들었던 생각은 각 색종이 area를 구하여 더함 교집합 영역을 구함 하나의 교집합 영역만 전체 area에 남겨두고, 나머지는 뺌 그런데 이렇게 처리하면 예외 케이스가 많이 생겨 너무 복잡도가 증가한다는 단점이 있었습니다. 단순하게 생각해보면, A라는 100 x 100 매트릭스가 있다고 가정했을때, 겹치든 겹치지지 않든, 색종이가 영역을 덮고 있다면 A[i][j] 의 값을 1로 설정하고 그렇지 않다면 0으로 설정하면 불필요한 예외 처리 없이 문제를 해결 할 수 있습니다. 정답 코드는 다음과 같습니다. if __name__ == '__main__..

[백준 10798번] 세로 읽기 파이썬

백준 단계별로 문제를 풀기 시작하다보면, 2d-array에 관한 문제가 나옵니다. 단계별로 올라갈수록 맛보기 수준의 문제에서 난이도가 올라가는 것을 체감할 수 있습니다. 오늘은 10798번 문제에 대해 어떻게 풀었는지 공유해보겠습니다. (https://www.acmicpc.net/problem/10798) 다음 문제에서 챌린지는 matrix를 가로방향이 아닌 세로방향으로 읽어야함 각 행(단어)별로 0~15까지 가변 길이를 갖고 있음 문제는 두번째 포인트인데, 어떻게 예외를 처리할까 고민하게 될 수 있습니다. 답은 생각보다 간단합니다. if __name__ == '__main__': words = [input() for i in range(5)] for j in range(15): for i in rang..

python 리스트 요소 한 줄로 한번에 출력 print(*arr)

코딩 테스트를 풀다보면, 한 줄에 리스트 내 모든 값을 출력해야할 때가 있습니다. 이럴 때 보통 접근하는 방법은 아래처럼 for문을 활용하는 경우가 있습니다. arr = [1, 2, 3, 4, 5] for i in range(len(arr)): print(i, end=" ") 이렇게 for 문을 돌리지 않고 출력하는 방법은 사실 매우 간단합니다. 단순하게 출력하고자하는 리스트 앞에 *를 붙여주어 print문에 넣어주면 됩니다. --> print(*arr) arr = [1, 2, 3, 4, 5] print(*arr) # 1 2 3 4 5 print(arr) # [1, 2, 3, 4, 5] 리스트에 별표 (asterick; *)를 활용하면 리스트 압축을 해제하기 때문입니다.

[python] stack 구현 (고정길이 스택 fixed stack, class 활용)

(본 포스팅은 Do It! 시리즈의 '자료구조와 함께 배우는 알고리즘 입문 - 파이썬편'을 참고하여 작성하였습니다.) 데이터를 임시 저장하는 기본 자료 구조는 대표적으로 두 가지가 있는데, 스택(stack)과 큐(queue)이다. 스택은 일반적으로 데이터 입력과 출력 순서가 후입선출(Last in First Out)인 것이 특징이다. 이 기능을 구현하기 위해서 우리가 생각해봐야할 부분은 어떤 것이 있을까? 크게 살펴보자면 첫째로, 데이터를 집어 넣는 push 기능 둘째로, 데이터를 꺼내는 pop 기능 셋째로, 스택의 길이를 알려주는 len 기능 넷째로, 스택이 비었는지 확인하는 기능 다섯번 째로, 스택이 가득 차 있는지 확인하는 기능 여섯번 째로, 특정 값이 스택 어디에 위치해있는지 확인하는 기능 일곱번..