백준136 [백준] 9663 N-Queen 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 전형적인 N-Queen 문제로 완전 탐색, 백트래킹 사용 2) 알고리즘 완전 탐색 백트래킹 3) 풀이 코드 사용 언어 - Python import sys def chk(y, x): for i in range(1, y+1): if x - i >= 0 and cols_selected[x] - i == cols_selected[x-i]: # 현재 열의 행과 옆에 떨어진 열의 행이 같을때 return False # 위로 올라갈수록 대각선에 퀸이 있을때 elif x + i < N and cols_selected[x] - i == cols_selected[x+i]: return False return True def solution(n): global answe.. 2022. 1. 2. [백준] 1759 암호 만들기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 암호가 알파벳 증가하는 순서로 배열되었다고 하므로, 초기에 알파벳들을 사전순으로 사전 정렬 문제의 해당 조건에 충족하는 모든 문자를 찾아야하므로 완전 탐색으로 접근 2) 알고리즘 완전 탐색 (Brute force) 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(n, idx, ans): # 현재 알파벳 선택한 개수, 시작할 인덱스 번호, 지금까지 만든 단어 global vowel_cnt, consonant_cnt if n >= L: # 원하는 길이 만들어졌으면 확인 if vowel_cnt and consonant_cnt >= 2: # 모음이 1개 이상, 자음이 .. 2022. 1. 1. [백준] 10819 차이를 최대로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 숫자들을 정렬하여 큰수와 작은수를 적절히 이용하여 계산하는 방식으로 접근 문제가 해결되지 않는것을 알아내서 완전 탐색 이용 2) 알고리즘 브루트포스 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def DFS(n, pre, ans): # 숫자를 선택한 횟수, 이전에 선택한 값, 지금까지 계산한 결과 값 global answer if n >= N-1 and answer 2021. 12. 31. [백준] 7662 이중 우선순위 큐 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 값을 추가하고 최솟값과 최댓값을 삭제하는 연산이 존재하여 최소힙을 이용해 데이터를 다루도록 접근 최소힙과 최대힙 2개를 사용하려 했으나 각자의 리스트에서 어떤 값들이 이미 삭제된건지 판별하기 어려울것 같아서 최소힙 하나로 진행 최소힙에서 최댓값 삭제할때는 내장된 max 함수와 리스트의 remove 함수를 이용해 제거하는 방식으로 접근하였으나 시간초과로 실패 최소힙과 최대힙 두개를 사용하는대신 어떤게 삭제 되었는지 판별하는 로직 추가하여 접근 2) 알고리즘 최소힙 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') T = int(sys.stdin.readline()).. 2021. 12. 30. [백준] 1747 소수&팰린드롬 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 소수를 구해야 하므로 '에라토스테네스의 체'를 이용하여 소수 판별 팰린드롬인 수를 구하기 위해 10으로 나눈 나머지 및 몫을 이용해 숫자 역으로 배치하여 판별 2) 알고리즘 에라토스테네스의 체 3) 풀이 코드 사용 언어 - Python import sys N = int(sys.stdin.readline()) # 특정 숫자 prime_num = [1] * 1003002 # 정답이 나올 수 있는 최대 숫자까지만 리스트 생성 prime_num[0] = prime_num[1] = 0 # 0, 1은 소수가 아니므로 for i in range(2, int(1003002**0.5) + 1): # 에라토스테네스의 체 if prime_num[i]: mul = 2 wh.. 2021. 12. 29. [백준] 6497 전력난 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 마을마다 모두 하나씩 길이 연결되어 있어야하고, 그 길의 유지비용이 가장 적게 할 수 있는 경우를 구해야 하므로 '최소 신장 트리' 알고리즘으로 접근 2) 알고리즘 최소 신장 트리 (Minimum Spanning Tree) 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def kruskal(start): # 힙을 이용한 크루스칼 알고리즘 구현 global min_cost heap = [(0, start)] # 최초 시작 지점 초기화 while heap: node = heapq.heappop(heap) if not visited[node[1]]: # 아직 연결되.. 2021. 12. 28. [백준] 2636 치즈 문제 풀이 과정 1) 문제 이해 및 접근 치즈의 가장자리를 구해야하므로 델타 탐색을 이용해 현재 위치가 치즈이고 주변이 치즈가 없는 경우에 가장자리로 나타내는 방식으로 접근 그러나 중간에 치즈가 없는 비어있는 구간이 발생시 치즈 안쪽에도 가장자리라고 인식하는 문제 발생 치즈 가장자리를 구하는 로직 고민 중 역으로 치즈가 아닌곳에서 DFS 탐색을 하여 가장자리를 구하는 방식으로 접근 시간이 흐름에 따라 가장자리였던곳만 다시 DFS 탐새으로 새로운 가장자리를 구하는 방식으로 접근 2) 알고리즘 DFS 구현 시뮬레이션 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def DFS(y, x): cheese_boundary = set() # 치즈.. 2021. 12. 26. [백준] 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 ··· 8 9 10 11 12 다음
