python178 [백준] 2573 빙산 문제 풀이 과정 1) 문제 이해 및 접근 빙산이 하나의 덩어리로 뭉쳐있는지 확인이 필요하여 DFS 탐색을 이용하여 확인 또한, 시간이 흐름에 따라 빙산이 녹아야 하므로 2차원 배열을 돌면서 값을 줄이려고 함 2차원 배열을 계속해서 반복하면 시간초과가 우려되어, 주변에 0의 개수를 기억하게 하여 시간을 줄이려고 시도 그리하여 초기에 시간의 흐름에 따라 2차원 배열을 모두 반복해서 빙산이 녹게 만들어주고, 다시 DFS 탐색으로 덩어리 분리 여부를 확인하는 방식으로 접근 그러나 배열의 크기가 최악의 경우 300 * 300 으로 반복적인 2차원 배열의 반복 확인으로 시간초과가 발생 빙산이 녹는 과정을 DFS 탐색을 하면서 주변에 바다의 개수를 확인하여 빙산이 녹는 과정과 덩어리를 확인하는 과정을 하나로 합쳐서 .. 2021. 12. 25. [백준] 14503 로봇 청소기 문제 풀이 과정 1) 문제 이해 및 접근 청소기가 현재 위치를 기준으로 하여 동, 서, 남, 북의 4개의 방향을 바라보며 이동하므로 델타 탐색을 이용하는 방식으로 접근하였습니다. 특정 조건에 충족되면 앞으로 진행을 하기 때문에 재귀를 이용한 DFS 탐색으로 접근했습니다. 2) 알고리즘 델타 탐색 DFS 재귀 호출 구현, 시뮬레이션 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def DFS(y, x, direction): # 좌표, 바라보는 방향 global answer for k in range(1, 5): # 왼쪽 방향을 4번 확인 해야 하므로 4번 반복 new_direction = (direction - k) % 4 # 새로운 방.. 2021. 12. 24. [백준] 1715 카드정렬하기 문제 풀이 과정 1) 문제 이해 및 접근 가장 작은 수들을 우선으로 더해주면 되므로 그리디로 접근했습니다. 연산한 수를 리스트에 다시 넣고 그 중 가장 작은 수를 다시 빼서 사용해야 하므로 최소 힙을 사용했습니다. 2) 알고리즘 그리디 알고리즘 최소 힙 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 숫자 개수 heap = [] # 힙으로 사용할 리스트 answer = 0 # 정답 변수 for _ in range(N): # 숫자들을 모두 최소힙에 푸시 heapq.heappush(heap, int(sys.stdin.readline())) while len(he.. 2021. 12. 23. [백준] 10868 최솟값 문제 풀이 과정 1) 문제 이해 및 접근 여러번 구간에 따라 최솟값을 구해야하므로 세그먼트 트리로 접근하였습니다. 2) 알고리즘 세그먼트 트리 (Segment Tree) 3) 풀이 코드 사용 언어 - Python import sys from math import log2, ceil sys.stdin = open('input.txt') def initial_tree(node, left, right): # 현재 노드 / 범위 시작 / 범위 끝 if left >= right: # 리프 노드일때 segment_tree[node] = lst_num[left] # 현재 노드에 숫자 값 할당 return segment_tree[node] # 할당된 현재 노드의 값 반환 left_node = initial_tree(n.. 2021. 12. 22. [백준] 2357 최솟값과 최댓값 문제 풀이 과정 1) 문제 이해 및 접근 여러가지 경우의 범위를 여러번 조회를 하여야 하므로, 세그먼트 트리를 이용하여 접근했습니다. 이전에 학습한 숫자의 합을 저장하는것과 다르게 최솟값, 최댓값을 구해야했기에, 노드의 값으로 숫자가 아닌 리스트를 저장하는 형태로 접근했습니다. 2) 알고리즘 세그먼트 트리 (Segment Tree) 3) 풀이 코드 사용 언어 - Python import sys from math import ceil, log2 sys.stdin = open('input.txt') def initial_tree(node, start, end): # 세그먼트 트리 만들기, 현재 노드 번호 / 범위 시작 / 범위 끝 if start >= end: # 리프 노드에 도달했을때 segment_tre.. 2021. 12. 21. [프로그래머스] 트리 트리오 중간값 문제 풀이 과정 1) 문제 이해 및 접근 세개의 노드를 선택하여야 하므로, 모듈을 이용해 조합의 경우의 수를 구하는 방식으로 접근했습니다. 또한 모든 점에 대해서 어떤 점을 향하는 거리의 값이 필요하여 다익스트라를 이용하는 방식으로 생각했습니다. 그러나 노드의 개수가 너무 많아, 너무 많은 다익스트라 함수를 실행하여 시간 초과가 발생하였습니다. 이 문제를 해결하기 위해 고민하던 중 트리의 지름에 관한 문제를 접하고, 활용하게 되었습니다. 세개의 노드의 길이 중 최댓값을 구하면 되었으므로 트리의 지름을 구하고 트리의 지름 -1 의 길이를 구하는 방식으로 접근하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python (1) 다익스트라, 조합 이용한 접근 - 시간 초과 import hea.. 2021. 12. 20. [백준] 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 ··· 12 13 14 15 다음
