백준136 [백준] 2042 구간 합 구하기 문제 풀이 과정 1) 문제 이해 및 접근 초기에 구간합 문제로 누적합을 이용하여 접근을 시도했습니다. 누적합을 구하고 계속되는 추가 값 수정 및 구간합을 구하는 과정에서 많은 연산이 진행될거라 예상해서 예상 연산 횟수를 고려해봤습니다. 그러나 중간에 어떠한 수가 변경하게 되면 특정 수 이후의 모든 누적합이 변경해야 하거나, 다른 변수에 저장할 경우 특정 구간의 모든 수를 확인해야하는 단점이 예상되었고, 문제 조건에 따라 수의 개수 (최대 1,000,000) X 구간합 구하는 횟수 (최대 10,000) 으로 최악의 경우 10,000,000,000(10억의 연산)번으로 시간 초과 발생을 예상했습니다. 이후 다른 알고리즘을 알아보던 중 '세그먼트 트리' 알고리즘을 알게 되어 학습 후 적용시켰습니다. 2) 알고.. 2021. 12. 19. [백준] 1167 트리의 지름 문제 풀이 과정 1) 문제 이해 및 접근 최초 문제를 접하였을때, 두개의 노드에서 가장 먼 거리를 구해야 하므로 DFS 탐색을 하여 가장 먼 거리를 구하는 방식으로 생각했습니다. 출발 노드가 어디냐에 따라 먼 거리가 달라질 수 있으므로 완전 탐색 방식으로 접근했습니다. 그러나 모든 노드를 완전 탐색하여야 했기 때문에 시간 초과가 발생했습니다. 시간 초과 문제를 해결하기 위해 고민 한 결과 모든 노드를 출발지로 선택하여 DFS 탐색을 해햐하는것이 비효율적이라 판단됬습니다. 고민한 결과 트리의 지름을 구하려할때 트리의 특징을 발견했습니다. 어떠한 노드에서 최초 1회 탐색을 하였을때, 가장 멀리 있는 노드의 번호를 알아내고 그 노드로 다시 한번 DFS 탐색을 하였습니다. 이러한 방식을 이용하면 트리에서 가장 .. 2021. 12. 18. [백준] 9934 완전 이진 트리 문제 풀이 과정 1) 문제 이해 및 접근 문제에서 '완전 이진 트리' 및 주어진 조건, 노드의 총 개수 등을 확인하였을때, '포화 이진 트리' 라고 판단하였습니다. 트리의 중위 순회의 특징인 왼쪽 "자식 노드 / 부모 노드 / 오른쪽 자식 노드" 고려하여 재귀를 이용하는 풀이 방법을 생각했습니다. 2) 알고리즘 트리 순회 (중위 순회, In_order) 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') # 중위 순회를 하며 각 노드를 층별로 배치 시키는 함수 def solution(left, root, right, depth): # 왼쪽 자식 노드 시작 인덱스 / 부모 노드 인덱스 # 오른쪽 자식 노드 끝 인덱스 / 트리의 레벨 if.. 2021. 12. 17. [백준] 1535 안녕 문제 풀이 과정 1) 문제 이해 및 접근 세준이의 체력 한도안에서 최대의 기쁨을 얻기 위해 어떠한 사람들을 만났을때, 얻을 수 있는 최대 기쁨을 구해야 하므로 전형적인 배낭 문제(knapsack) 알고리즘을 활용하여 문제를 풀어나갈 수 있음 2) 알고리즘 배낭 문제 (Knapsack) 3) 풀이 코드 사용 언어 - Python 2차원 배열을 이용한 풀이 import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) L = list(map(int, sys.stdin.readline().split())) # 사용 되는 체력 J = list(map(int, sys.stdin.readline().split())) # 얻게 되는 기쁨 pleasure.. 2021. 12. 16. 이전 1 ··· 9 10 11 12 다음
