jungle python loop break function return 백준 1715 9012 2504 1655 10830 algorithm

파이썬 알고리즘 3주차 : 카드 정렬하기, 괄호, 괄호의 값, 가운데를 말해요, 행렬 제곱

정글일지 13

1.개발 진행 및 완료상황

  • 2주차 python algorithm 종료
  • 3주차 python algorithm 시작

  • 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용

  • 백준 1715

1715번: 카드 정렬하기

1715번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 카드 정렬하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 46099 15534 11930 33.435% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶…

www.acmicpc.net

최소 heap을 이용하였다. 카드를 가장 적게 더하는 방법은 작은 수부터 오름차순으로 올라가는 것이다. 문제를 보고 빠르게 파악했지만, sort를 사용하면 시간초과로 오답처리 되었다. 최소 heap을 이용하면 정렬과정 없이 최솟값이 가장 앞으로 나오므로 문제를 풀 수있다. 정답코드는 다음과 같다.

import sys import heapq n = int(sys.stdin.readline()) #입력값 heap = [] for _ in range(n): heapq.heappush(heap,int(sys.stdin.readline().rstrip())) # 위 3줄은 입력값을 최소heap으로 정렬하는 과정이다. ans = 0 if n == 1: ans = 0 #카드뭉치가 1개면 더할 이유가 없다. elif n == 2: #카드뭉치가 2개면 2개를 더하면 된다. min_1 = heapq.heappop(heap) min_2 = heapq.heappop(heap) ans = min_1 + min_2 else: for _ in range(n-1): min_1 = heapq.heappop(heap) #최소힙이므로 바로 최소값을 알수 있음. min_2 = heapq.heappop(heap) #heappop하면 다시 heap정렬함 sum = min_1 + min_2 #가장 작은 두 수를 더한 후 ans += sum # 현재까지 비교횟수를 반영 heapq.heappush(heap,sum) #더한 값을 다시 집어넣는다. print(ans)

  • 백준 9012

9012번: 괄호

9012번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 괄호 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 156001 72317 52159 45.298% 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x…

www.acmicpc.net

스택을 이용하여 방금 push한 괄호와 현재 괄호를 비교하여 VPS인지 여부를 확인하였다. 비교 전 stack에 원소값이 있는지 확인하는 과정도 필요하다. 빈 stack에 여는 괄호(‘(‘)일때 ‘1’을 push했고 닫는 괄호(‘)’)면 pop했다. pop할 게 없다면 VPS가 아니란 뜻이므로 반복을 종료했다. 정답코드는 다음과 같다.

import sys T = int(sys.stdin.readline()) data = [] for _ in range(T): #입력된 괄호 data.append(sys.stdin.readline().rstrip()) for i in data: cal = [] x = list(i) #각 괄호를 원소로 하는 리스트 생성 for a in x: if a == ‘(‘: cal.append(‘1’) #여는 괄호는 빈 스택에 ‘1’ push else: #닫는 괄호의 차례라면 if len(cal) == 0: # 스택이 empty라면 짝이 없다는 뜻 cal = [1] break # else: # 스택에 원소가 있다는 것은 앞에 여는 괄호 있었음 cal.pop() # 짝이 맞았으므로 스택에서 하나를 지운다. if len(cal) > 0: print(‘NO’) else: print(‘YES’)

  • 백준 2504

2504번: 괄호의 값

문제 4개의 기호 ‘ ( ’, ‘ ) ’, ‘ [ ’, ‘ ] ’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘ () ’와 ‘ [] ’는 올바른 괄호열이다. 만일 X 가 올바른 괄호열이면 ‘ (X) ’이나 ‘ [X] ’도 모두 올바른 괄호열이 된다. X 와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY 도 올바른 괄호열이 된다. 예를 들어 ‘ (()[[]]) ’나 ‘ (())[][] ’ 는 올바른 괄호열이지만 ‘ ([)] ’ 나 ‘ (()()[] ’ 은 모두 올바른 괄호…

www.acmicpc.net

앞의 괄호 문제와 유사하면서도 조금 더 복잡했다. 내부가 빈 괄호는 숫자로 바꿨는데 내부에 숫자를 가진 괄호를 곱셈이라 처리하는 게 힘들었다. 또한 올바르지 못한 괄호열도 확인해야했다. 우선 1이라는 임시변수를 설정했다. 그리고 괄호를 열 때 마다 ‘(‘는 *2, ‘[‘는 *3 을 해주었다. 그리고 올바르게 닫히면 pop을 하여 앞에 있던 여는 괄호를 없애고 지금까지 한 값을 최종 정답 변수에 넣어준 후 다시 곱했던 수로 나누어주었다. 이 이후의 값들은 괄호 밖이므로 곱해지면 안되기 때문이다. 예를 들어, (())의 경우

122 =4 => (() 까지의 과정이다. 괄호가 닫혔으니 정답 변수에 더해준다.

4//2 = 2

2 => 앞서 결과가 2까지였는데, 닫힌 괄호가 다시 나왔다. 앞에 여는 괄호가 하나 남아있으니 2를 정답 변수에 더해준다. 그리고 나눠주면 다시 1이 된다.

이 과정을 통해 정답은 4+2 = 6 임을 알 수 있다. 이 괄호 이후의 숫자는 곱하기가 아니라 더하기이므로 나누기를 반드시 해주어야한다. 정답코드는 다음과 같다.

import sys stack = [] # 스택 res = 1 # result에 더해주기 전 임시 변수 result = 0 # 정답 변수 p = list(sys.stdin.readline()) # 입력값 for i in range(len(p)): if p[i]==’(‘: #여는 괄호라면? res _= 2 #우선 곱해준다. stack.append(p[i]) #스택에 넣어준다. elif p[i]==’[’: res _= 3 stack.append(p[i]) elif p[i]==’)’: if not stack or stack[-1]!=’(‘: #닫는 괄호가 나왔는데 스택이 비었거나 앞 원소가 짝이 안맞을때 result = 0 # 올바르지 못한 괄호이므로 break if p[i-1]==’(‘: result += res #올바르게 닫혔으므로 정답 변수에 더해주고 res //= 2 #그 후 나눠주어 이후에는 곱하기가 영향을 못끼치도록 한다. stack.pop() #짝을 맞추어 사용했으니 pop해준다. elif p[i]==’]’: if not stack or stack[-1]!=’[’: result = 0 break if p[i-1]==’[’: result += res res //= 3 stack.pop() # 결과 출력 if stack: # 스택에 원소가 남아있다면 올바르지 못한 괄호 print(0) else: print(result)

  • 백준 1655

1655번: 가운데를 말해요

1655번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 가운데를 말해요 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.1 초 ( 하단 참고 ) 128 MB 49937 14517 10911 30.409% 문제 백준이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1…

www.acmicpc.net

현재까지 입력된 수의 갯수가 중요하다. 짝수일 경우 두 수중에 작은 수를 출력해야하고 홀수라면 중간값을 말하면 된다. 최소 heap을 두개를 설정해주었다. 왼쪽, 오른쪽에 하나씩 순서대로 숫자를 넣었다. 전체 갯수가 홀수라면 왼쪽 최소heap의 루트를 출력하면 되고, 전체 갯수가 짝수라면 양쪽 최소 heap의 루트 중 더 작은 수를 출력하면 된다. 최소 힙의 root는 최소값이기 때문이다. 정답 코드는 다음과 같다.

import sys import heapq

n = int(sys.stdin.readline())

leftheap = [] rightheap = []

for _ in range(n):

1

# 현재 숫자

​ num = int(sys.stdin.readline())

1

# leftheap의 길이가 rightheap의 길이와 같다면

​ if (len(leftheap) == len(rightheap)): # leftheap에 현재 숫자를 음수 형태로 삽입 ​ heapq.heappush(leftheap, -num)

1

# leftheap의 길이가 rightheap의 길이와 다르다면

​ else: # rightheap에 현재 숫자를 삽입 ​ heapq.heappush(rightheap, num)

1
2

# 양쪽 heap에 요소들이 존재한다면,
# leftheap의 루트에 음수를 곱한 값이 rightheap의 루트보다 크다면

​ if (len(leftheap) >= 1 and len(rightheap) >= 1 and -leftheap[0] > rightheap[0]):

1

    # leftheap의 루트를 제거하고,

​ leftroot = heapq.heappop(leftheap) # leftheap의 루트에 음수를 곱한 값을 rightheap에 삽입 ​ heapq.heappush(rightheap, -leftroot)

1

    # rightheap의 루트를 제거하고,

​ rightroot = heapq.heappop(rightheap) # rightheap의 루트에 음수를 곱한 값을 leftheap에 삽입 ​ heapq.heappush(leftheap, -rightroot)

1

# leftheap의 루트에 음수를 곱한 뒤 출력

​ print(-leftheap[0])

  • 백준 10830

10830번: 행렬 제곱

10830번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 행렬 제곱 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 28226 9978 7911 34.157% 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의…

www.acmicpc.net

행렬을 리스트로 표현하는데 생각이 너무 복잡했던 문제다. 리스트 안에 각 행의 숫자 나열을 리스트 형태로 입력하면 생각보다 쉽게 표현은 가능하다. 정사각 행렬의 곱셈은 각 행과 열의 곱이고 이는 결과가 나타나는 자리의 행,열과 같다. 1000으로 나눈 나머지를 구해야 하는데 행렬에만 신경쓰다보면 값을 구한 후 나누려고해 시간초과가 뜰 수 있다. %1000이 포함된 두 행렬의 곱셈 결과를 나타내는 함수를 설정하고, 제곱규칙을 이용해 계산횟수를 줄일 수 있는 함수를 구성하였다.

import sys N,B = list(map(int,sys.stdin.readline().split())) matrix = [] for _ in range(N): matrix.append(list(map(int,sys.stdin.readline().split()))) def mul(U, V): n = len(U) Z = [[0]*n for _ in range(n)] for row in range(n): for col in range(n): e = 0 for i in range(n): e += U[row][i] * V[i][col] Z[row][col] = e % 1000 return Z def square(A, B): if B == 1: for x in range(len(A)): for y in range(len(A)): A[x][y] %= 1000 return A tmp = square(A, B//2) if B % 2: return mul(mul(tmp, tmp), A) else: return mul(tmp, tmp) result = square(matrix, B) for r in result: print(*r)

  1. 새로 배운 내용
  • break, return, continue: return은 함수의 실행을 중단하고 함수의 결과로 값을 지정한다. break문은 가장 가까운 반복문을 탈출한다. 즉 이중 반복문의 경우 하나만 탈출한다. continue는 ‘이번’ 반복만 중단한다. for문에서 많이 쓰는데 이번 변수에서만 중단하고 다음 변수로 넘어갈 때 사용한다.
  1. 참고할 만한 레퍼런스들
  1. 3주차 파이썬 알고리즘 공부
  2. 3주차 파이썬 알고리즘 문제 풀이
  3. CSAPP 읽기
CATALOG
    log