본문 바로가기

알고리즘, 문제 풀이기록

 (51)
#27: 다리놓기 답안을 확인했다. 서두의 '조합'이라는 단어를 보는 순간 바로 코딩을 시작했다. 바로 전 문항의 이항계수 코딩을 활용하면 됐다. 다음은 코드이다. import math T = int(input()) for _ in range(T): N, M = map(int, input().split()) if 0
#26: 이항계수 import math N, K = map(int, input().split()) if 0
#25: 최소공배수 유클리드 방식의 최대공약수 구하는 방식을 이해해야겠다 생각하여 파이썬으로 그 방식을 구현한 코드를 이해하려 하였다. 하지만 우선 그 수학적 논리를 이해하는게 우선이라 생각하여 다음 자료를 찾았다. 이것을 구현한 코드가 다음과 같다. def gcd(x, y): while y: x, y = y, x % y return x 항해99 슬랙에다 질문해본 결과 1. while y란 y = 0일 때 무한 loop에서 빠져나온다는 의미이다. 2. x, y = y, x%y란 x = y와 y = x % y를 한 번에 표현한 것이다. 그러고 나면 최소공배수는 두 수의 곱에서 최대공배수를 나눈 값과 같다. 결과 코드는 다음과 같다. T = int(input()) def gcd(x, y): while y: x, y = y, x..
#24: 괄호 T = int(input()) for _ in range(T): P = input() ls = list(P) sum = 0 for i in ls: if i == '(': sum += 1 elif i == ')': sum -= 1 if sum 0: print("NO") elif sum == 0: print("YES") 답안을 참조해가며 일단 완성시킨 코드이다. 1. sum = 0 을 for문 안에 위치시켜야 한다. 2. for문 안의 세번째 if문이 핵심이라 생각한다. 문제가 스택으로 분류되있었는데 이 세줄에서 그 이유를 알 수 있다. '선형성'을 이해해야 한다 생각한다. 괄호는 '(' -> ')' 순으로 진행된다. 즉 시작 괄호 없이 끝 괄호가 먼..
#23: 제로 import sys stack = [] K = int(sys.stdin.readline()) for _ in range(K): N = int(sys.stdin.readline()) if N == 0: stack.pop(-1) else: stack.append(N) print(sum(stack)) 답안을 확인하고 수정하여 정답이 된 코드이다. 다섯째 줄의 로직을 이해하고 원래 코드를 수정하니 문제가 해결이 되었다. 원래는 if문에 sys문을 포함시켰지만 if문 전에 변수 N을 미리 정의를 해주니 코드가 훨씬 간결해졌고 수정 전의 오류를 해결할 수 있었다.
#22 스택 import sys N = int(sys.stdin.readline()) stack = [] for _ in range(N): input = sys.stdin.readline().split() if input[0] == "push" + "int": stack.append(int) if input("top"): print(stack[-1]) if input("size"): print(stack.count()) if input("empty"): if stack.count() == 0: print("1") else: print("0") if input("pop"): if stack.count() != 0: stack.pop(stack[-1]) else: print("-1") 미완인 코드를 첨부한다. 처음에 i..
알고리즘 주간 #21 나무 자르기 이진 검색(이분 탐색) 기법을 활용하는 문제이다. 이분탐색이란 말그대로 리스트를 이분하여 탐색하는 것이다. 책을 참고하고 박현준 튜터의 강의를 한 번 들어보기도 하면서 개인 학습을 어느정도 하였다. 그러고 문제를 읽는데 시간을 소모하였고 어느 정도 풀이에 대해 생각하다가 답안을 확인하였다. 이분탐색을 활용한 코드였는데, while문 안에 for문, if문이 어떠한 구조를 갖고 코딩돼있었는데, 완전히 이해가 되지는 않았다. 40번 갈 때까지 이분탐색 문제가 없는 것으로 확인했다. 나중에 다시 돌아와서 그때는 이분탐색 개념적 기반을 확실히 다지는 것에 중점을 둬야겠다.
알고리즘 주간 #20 좌표 정렬하기 2 역시 답안을 확인하였다. import sys 하여 sys.stdin.readline()으로 입력값의 총 줄수를 결정해주는 n값을 input 해주었다. 그리고 list(map())으로 나머지 줄 input을 구현하였다. 그리고 map 메서드는 append(list()) 메서드가 감싸고 있는데 이를 통해 생성된 list를 key = lambda를 활용하여 sort해준다. 이때 lambda는 함수를 생성할 때 사용하는 예약어로 def와 동일한 역할을 하는 것으로, 보통 함수를 한줄로 간결하게 만들 때 사용한다. 일단 이 정도만 하고 넘어가겠다. 백준 알고리즘 한두번으로 끝낼 생각하면 안될 듯 하다.

티스토리툴바