본문 바로가기

알고리즘, 문제 풀이기록

 (51)
#35. N과 M(2) N, M = map(int, input().split()) ls = [] for i in range(M): for j in range(N): print(j) 위는 시도해본 코드이다. 이후 답안을 참조하였다. 문제의 주제인 Backtracking을 위해 DFS(Definitive Feasibility)를 활용하더라. 로직이 이해가 잘 가진 않는다. dfs에 대한 개념이 부족해서이리라. dfs에 대한 개념을 숙지하고 돌아왔을 때는 문제 풀이가 수월할 것이다.
#34: 색종이 만들기 문제를 이해하고 matrix를 써야한단 생각을 했지만 이내 답안을 확인했다. global 키워드를 쓰더라. 이게 변수의 범위를 설정해준다. 또 '쿼드트리(Quad-Tree)'라는 용어를 쓰더라. 네 사분면으로 분할해주어서 이 용어를 쓰는 듯 하다. 하지만 matrix[y][x]에서 대괄호 열고 닫은 것 두 개를 이은 것이 어떤 역할을 하는 것인지 등 기본적인 문법에 대한 이해가 부족하여 코드의 로직 자체를 이해하는데 문제를 겪고 있다. 알고리즘 학습을 꾸준히 진행하면서 파이썬 문법을 더욱 숙달시킨 후에 다시 풀이를 시도해보겠다.
#33: 통계학 먼저 혼자 진행한 코드를 첨부한다. N = int(input()) ls = [] for _ in range(N): num = input().split() ls.append(num) print(round(sum(ls) / ls.count(), 1)) ls.sort() first_i = ls.index(0) last_i = ls.index(-1) print((first_i + last_i) / 2) print() print() 이 정도로 진행을 하다가 답안을 확인했다. 확연히 달랐다. 먼저 문제에서 요구하는 네 가지 통계값들에 대해 각각 함수를 구현해주었다. 그 함수 내용의 로직을 이해하는데 별 문제는 없었다. 다만 Dictionary에 관한 코드, counter()등의 메서드를 숙지하는게 필요하다 싶었다...
#32: DFS와 BFS 박현준 튜터의 BFS, DFS 강의를 듣고 풀이에 돌입했지만 이내 답안을 확인하였다. matrix라는 list를 선언하고 그것을 중심으로 하는 풀이였다. 전의 Queue문제와 마찬가지로 BFS, DFS의 개념에 대한 이해을 기반으로 하는 코드라는 생각이 들었다. 1번~ 40번 반복하면서 BFS, DFS 문제 맞닦트릴 때마다 그것을 계속 숙지해가면서 소스코드를 이해하고 결국에 처음부터 끝까지 홀로 코딩할 수 있어야되겠다.
#31: 큐 2 다음은 한번 스스로 완성시켜본 코드이다. N = int(input()) queue = [] for _ in range(N): command = input().split() if command == "push" + str(int): queue.append(int) elif command == "pop": if len(queue) == 0: print(-1) else: print(queue[0]) queue.pop(0) elif command == "front": print(queue[-1]) elif command == "back": print(queue[0]) elif command == "size": print(queue.len()) elif command == "empty": if len(queue)..
#30: 회전하는 큐 답안을 확인했다. deque를 collections로부터 import해오더라. 확실히 '큐(Queue)'에 대한 개념을 기반으로 그것을 코드로 구현한다는 생각이 들었다. 박현준 튜터님의 '큐' 단원 강의를 다시 시청하였다. LinkedList개념을 기반으로 설명한단 생각도 들었다. 또 이 강의의 알고리즘/자료구조가 파이썬 클래스 개념에 대해 숙지가 되어 있어야 한단 생각도 들었고. 여튼 분명 큐를 학습하려고 한건데 다른 개념까지 줄줄이 딸려나온 꼴이다. 시바타 보요의 자료구조/ 알고리즘 책에도 문제와 같은 원형의 큐 자료구조에 대해서도 다루던데 이 책으로 해당 단원을 학습하는 것도 도움이 될 것이다.
#29: 스택 수열 문제를 이해하는데도 다른 문제에 비해 시간이 걸렸다. 답안 코드를 확인해보아도 이해가 잘 가지 않았다. 일단 list를 두 개 선언하는 것까지는 알겠는데 count와 num 변수를 두고 while문과 if문을 활용하여 이리저리 코딩한 것에 대해 이해를 하는데 문제를 겪었다. 이 문제는 시간을 두고 반복적으로 풀이를 시도해야 될 듯 하다.
#28: 균형잡힌 세상 답안을 확인한 문제이다. 하지만 코드 해독이 불완전한 상태로 이루어졌다. 특히 if not 문에서 시간을 소모하였다. 필자는 스택을 '선형성'으로 이해한다. 답안 코드는 문장의 선형성을 활용하여 for - if - if 구조로 경우를 나누어서 풀이를 하였다. 스택 문제의 경우 이름이 stack인 list를 선언해주는 것이 기본인 듯하다. 또한 여러 줄에 걸친 input을 어떻게 해야할지 몰랐는데 sys.stdin.readlines()를 해주면 되었다. 시간이 너무나 지체되어 일단 이까지만 하고 넘어가기로 한다.

티스토리툴바