백준136 [백준] 22944 죽음의 비 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 상하좌우를 이동하면서 우산 내구도와 남은 체력을 확인하며 한칸씩 이동하도록 진행하였습니다. 초기에 DFS를 이용하고, 몇몇 조건을 주어 백트래킹을 시도하였으나 배열의 크기가 최대 500 * 500 이고, 새로운 우산 내구도 적용시 방문했던 위치를 다시 방문이 가능해 더 많은 연산을 하기 때문에 시간초과가 발생했습니다. 이를 해결하기 위해 BFS 탐색으로 변경을 시도하였고, 약간의 메모이제이션을 활용하여 연산의 횟수를 줄이도록 시도하였습니다. 2) 알고리즘 BFS 메모이제이션 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def s.. 2022. 1. 18. [백준] 6443 애너그램 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 단어의 글자들의 위치를 바꿔서 나오는 단어를 구해야 하므로 순열을 사용하였습니다. 중복되는 결과를 막기 위해서 집합을 사용하였습니다. 초기에 단어를 정렬하여 알파벳순으로 정렬하도록 했습니다. 또한, 시간을 줄이기 위해 집합으로 각 자릿수로 사용한 단어를 계속해서 추가했습니다. 2) 알고리즘 순열 백트래킹 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(n, ans): if n 2022. 1. 15. [백준] 15649 N과 M (1) 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수열을 구해야하기 때문에 재귀를 이용하여 풀었습니다. 2) 알고리즘 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(n, ans): if n 2022. 1. 14. [백준] 1275 커피숍2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 계속해서 값들이 변경이 일어나고, 랜덤한 범위의 합계를 구해야하므로 세그먼트 트리를 이용했습니다. 2) 알고리즘 세그먼트 트리 3) 풀이 코드 사용 언어 - Python import sys from math import ceil, log2 sys.stdin = open('input.txt') def init_tree(node, start, end): # 세그먼트 트리 값 할당 if start >= end: # 리프 노드 도달시 segment_tree[node] = num_list[start] # 숫자 리스트의 값 추가 linked[start-1] = node # 각 숫자가 위치한 리프 노드의 인덱스 저장 return segment_tree[node] .. 2022. 1. 13. [백준] 11505 구간 곱 구하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어지는 입력에 따라 값을 계속해서 변경하고, 변경된 값을 토대로 구간의 곱을 구해야 하므로 세그먼트 트리로 접근했습니다. 2) 알고리즘 세그먼트 트리 3) 풀이 코드 사용 언어 - Python import sys import math sys.stdin = open('input.txt') def init_tree(node, start, end): # 세그먼트 트리 초기화 (현재 노드의 번호, 노드의 범위 시작, 노드의 범위 끝) if start >= end: # 리프 노드에 도달한 경우 segment_tree[node] = num_li[start] # 리프 노드에 숫자 값 넣기 linked[start-1] = node # 연결관계에 리프노드의 인덱스 .. 2022. 1. 12. [백준] 14502 연구소 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 비어있는 공간들 중 3군데를 벽을 세워야 하므로 모든 조합을 구하기 위해 벽을 세울 좌표 조합을 구했습니다. 바이러스가 여러곳에서 동시에 퍼져야 하므로 BFS 탐색을 하였습니다. 바이러스가 퍼지면 안전 구역의 개수를 하나씩 줄여가며 답을 찾아나갔습니다. 2) 알고리즘 조합 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque from itertools import combinations sys.stdin = open('input.txt') def solution(): global ans q = deque(start_coordinates) # 바이러스가 있는 모든곳에서 시작 (BFS).. 2022. 1. 11. [백준] 14600 샤워실 바닥 깔기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 안쪽으로 영역을 나누어서 타일을 설치해야하므로 분할정복으로 접근했습니다. 2) 알고리즘 분할정복 3) 풀이 코드 사용 언어 - Python import sys def solution(r, c, k, area): # 시작 좌표, 제곱 수, 구역 global num if k 2022. 1. 8. [백준] 17141 연구소2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열을 상하좌우를 탐색하여야 하고, 시간의 흐름에 따라 상하좌우 이동하며 바이러스를 퍼트려야 하므로 BFS 탐색으로 접근하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque from itertools import combinations sys.stdin = open('input.txt') def BFS(starts): # 너비 우선 탐색 global remain_empty visited = [[0] * N for _ in range(N)] # 좌표 방문 여부 체크 리스트 q = deque(starts) for n in q: # 첫 시작점 방문 체크 .. 2022. 1. 7. [백준] 1865 웜홀 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드간 가중치에 음수가 포함이 되어 다익스트라로는 해결이 어렵다고 생각하여 이전에 학습한 '벨만-포드' 알고리즘을 적용했습니다. 어떠한 지점에서 출발하여 다시 그 지점으로 돌아왔을때 시간이 줄어드는 경우를 찾아야 하는데, 만약에 한번 확인을 하여 계속 해서 값이 줄어드는 싸이클이 존재하는지 여부만 찾으면 된다고 생각했습니다. 2) 알고리즘 벨만-포드 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(): distance[1] = 0 # 출발 도시 거리는 0으로 초기화 for i in range(1, N+1): # 도시의 개수만큼 반복하여 확인 for j in ra.. 2022. 1. 6. [백준] 11657 타임머신 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드간 거리를 나타내는 간선의 가중치가 음수가 있는 경우도 있기 때문에, 다익스트라로는 어려울거라 생각했습니다. 간선 가중치에 음수가 들어간 경우 사용하는 벨만-포드 알고리즘을 학습하여 접근했습니다. 2) 알고리즘 벨만-포드 어떠한 노드에서 다른 노드로 이동하는 거리를 구할때 사용 (가중치가 음수가 있는 경우에도 사용 가능) 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start: int): # 벨만포드 (시작 노드) dist[start] = 0 # 시작 위치의 거리는 0으로 세팅 for i in range(1, N+1): # 도시의 개수만큼 반복하여 확인 .. 2022. 1. 5. [백준] 1504 특정한 최단 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 도착지점에 도착했을때, 필수로 방문해야하는 정점을 방문했는지 확인이 필요하여 최소힙을 사용하는 과정에서 방문한 정점의 리스트의 정보를 같이 최소힙에 저장을 시키는 방식으로 접근했습니다. 그러나 최소힙에 경로를 저장하는 리스트를 같이 할당하여 반복시켰기 때문에 메모리 초과가 발생했습니다. 이 문제를 해결하기 위해 정점 방문 기록을 삭제하고, 다익스트라를 최초 1번 정점, 필수 방문해야하는 정점 2개를 탐색하도록 접근하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start: int): # 다익스트.. 2022. 1. 4. [백준] 1043 거짓말 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 진실을 아는 사람들과 진실을 모르는 사람들이 어떤 파티에서 접촉하면 모두 진실을 알게 되므로, DFS 탐색으로 같이 겹치는 사람들을 구하려 접근 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(person: list): # 진실을 아는 사람들 구하는 함수 (진실을 아는 사람들) visited = [0] * (N+1) # 사람 확인했는지 체크용 리스트 stack = list(person.copy()) while stack: node = stack.pop() if not visited[node]: visited[node] = 1 for e in.. 2022. 1. 3. 이전 1 ··· 7 8 9 10 11 12 다음
