Sunrise

정렬 문제입니다. 이전 2750번 문제와 비교하면 N의 범위가 1000 → 100만으로 늘어났습니다. 이전 문제에서 사용했던 버블 정렬, 삽입 정렬은 최악의 경우 시간복잡도 O(N²)을 가지므로 이 문제에 똑같이 적용할 경우 시간 초과가 나게 됩니다. 따라서 이번 문제에서는 시간복잡도가 낮은 정렬을 사용해야 합니다. '버블 정렬, 삽입 정렬'보다 시간 복잡도가 낮은 정렬 알고리즘으로는 '병합 정렬, 퀵 정렬, 힙 정렬'이 있습니다. 그 중에서 이번에 사용할 방법은 1. 병합 정렬 (시간복잡도 O(N) = Nlog₂N) 2. 파이썬 기본 sort 사용 (시간복잡도 O(N) = Nlog₂N) 입니다. (참고로 범위 100만에 대해 Nlog₂N 연산은 100만 x 6 x log₂10 ≒ 2000만번 연산) 1..

정렬 문제입니다. 간단하게 파이썬의 sort() 메서드로 풀 수 있지만, 학습을 위해 버블 정렬, 삽입 정렬 알고리즘을 이용해 문제를 풀었습니다. 1. 버블 정렬 버블 정렬은 (0, 0) (0, 1) (0, 2) ... (0, n-1) (1, 0) (1, 1) ... (n-1, n-1) 의 쌍으로 비교해보면서 작은 값이 뒤에 있다면 앞으로 보내는 방식입니다. 버블 정렬은 구현이 간단하나 일반적으로 데이터 교환이 데이터 이동보다 더 복잡하기 때문에 잘 쓰이지 않습니다. 시간 복잡도는 O(N²)입니다. 2. 삽입 정렬 삽입 정렬은 손 안의 카드를 정렬하는 방법과 유사합니다. 두번째 숫자부터 바로 앞 숫자와 비교해 작으면 앞으로 보냅니다. 앞으로 보낼때 한 칸씩 보내면서 먼저 앞에 있던 것과 비교하여 더 큰 ..

이분탐색 문제입니다. 단순하게 list에 담아 if ~ in ~ 문법으로 간단히 구현하면 되는 줄 알았지만, 문제에서 범위가 N 10만, M 10만으로 주어졌기 때문에 M 하나하나에 대해서 N list에서 10만개 다 순차탐색을 하고 있으면 시간초과가 납니다. 이를 해결하기 위해서는 두 가지 방법이 있습니다. 첫째는 순차탐색이 아니라 이분탐색해서 시간복잡도를 O(N) → O(log₂N) 으로 줄이는 것 둘째는 A를 담을 때 set 자료형을 사용하여 시간복잡도를 O(N) → O(1) 으로 줄이는 것 먼저 첫 번째, 이분탐색 방법입니다. 숫자 UP & DOWN 게임과 비슷한 원리입니다. binary_search 함수를 만들고, A 범위의 중간점을 잡아 A의 중간값이 x인지 확인합니다. x가 아니라면 중간값이..

스택 문제입니다. 문제 예시를 보면서 막대기 개수가 언제 늘어나는지 관찰합니다. 자세히 관찰해보면, ')' 이 들어와서 레이저가 생기거나, 막대가 끊길 때 막대기 개수가 늘어나는 걸 볼 수 있습니다. 따라서 '(' 이 들어오면 count에 스택을 쌓다가 ')' 이 들어오면 전에 '(', ')'로 레이저가 만들어지는지 막대가 끊기는지 확인하면서 stick 총 개수를 더해줍니다. word = input() stack = [] count = 0 stick = 0 for x in word: if x == '(': # '(' 이면 스택에 넣기 count += 1 stack.append(x) else: # ')' 이면 레이저/막대기1개 확인 if stack[-1] == '(': # 레이저 -> 막대기 count 만..

스택 문제입니다. 먼저 count 변수를 따로둬서 스택 정보를 따로 관리합니다. 첫번째 받은 숫자까지 스택을 쌓고 다음에 받은 숫자부터 스택이나 pop으로 만날 수 있는거면 연산을 수행하면서 +, -를 기록합니다 만날 수 없는 경우 NO를 출력합니다. import sys input = sys.stdin.readline T = int(input()) num_list = [] stack = [] answer = [] count = 1 error_flag = False for _ in range(T): num_list.append(int(input())) for x in num_list: while count

스택 문제입니다. 들어온 A, B가 스택 맨 위와 같을 때 pop 해주고 스택이 비어있거나, 스택 맨 위가 들어온 것과 다르면 append 합니다. 결과적으로 짝이 맞아 모두 pop되어 스택이 비어있으면, 좋은 단어입니다. N = int(input()) count = 0 for _ in range(N): word = input() stack = [] for x in word: if stack and x == stack[-1]: # 스택 맨 위가 x와 같을 때 stack.pop() else: # 스택이 비어있거나, 스택 맨 위가 x와 다를 때 stack.append(x) if not stack: # 스택이 깔끔하게 비어있으면 좋은 단어 count += 1 print(count)

스택 문제입니다. '(' 이 들어오면 스택에 넣고 ')' 이 들어오면 스택에서 뺍니다. ')' 이 들어왔는데 스택이 비어있으면 error_flag 체크를 합니다. 결과 출력 시 error_flag 체크가 되어있거나, 짝이 안맞아 스택이 남아있으면 NO error_flag 체크 안되어있고, 스택도 빈 경우 YES T = int(input()) for _ in range(T): stack = [] error_flag = False word = input() for x in word: if x == '(': stack.append(x) else: if stack: stack.pop() else: error_flag = True # 스택 비어있을 때 ')' 들어오면 그 경우는 이미 틀림 if error_flag..

스택을 구현하는 문제입니다. 리스트를 선언하고 append, len, pop을 이용해서 스택의 기본적인 기능인 push, pop, size, empty, top 함수를 만들었습니다. import sys input=sys.stdin.readline # 시간초과로 추가 N = int(input()) stack = [] def push(x): stack.append(x) def pop(): if len(stack)==0: print(-1) else: print(stack.pop()) def size(): print(len(stack)) def empty(): if len(stack)==0: print(1) else: print(0) def top(): if len(stack)==0: print(-1) else..

https://covenant.tistory.com/234 참고 시작 & 구현 #1 2438 별 찍기 - 1 n = int(input()) for i in range(1, n+1): print("*"*i) #2 2439 별 찍기 - 2 n = int(input()) for i in range(1, n+1): # print(" "*(n-i), "*"*i) # 공백 추가돼서 에러남 print(" "*(n-i) + "*"*i) #3 2440 별 찍기 - 3 n = int(input()) for i in range(1, n+1): print("*"*(n-i+1)) #4 2441 별 찍기 - 4 n = int(input()) for i in range(n): print(" "*i + "*"*(n-i)) #5 24..

파이썬 기초부터 배울 수 있게 automata님이 정리해주신 백준 문제집입니다. Python 배우기 (1~50) - 백준 문제집 - automata 참고 https://www.acmicpc.net/workbook/view/459 #1 2557 Hello World print("Hello World!") #2 1000 A+B A, B = input().split() # split()으로 공백 구분하여 A, B에 담음 print(int(A)+int(B)) # 기본 입력 문자열형이라 정수형 변환 #3 10998 A*B A, B = input().split() print(int(A)*int(B)) #4 1001 A-B A, B = input().split() print(int(A)-int(B)) #5 1008 ..