알고리즘 문제풀이/Python179 [백준] 1707 이분 그래프 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 이분 그래프를 찾아야하므로 DFS 탐색을 통해 노드들을 탐색하였고, 인접한 노드마다 방문처리를 다르게 하여 이분그래프 여부를 판별했습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): # DFS 탐색 stack = [start] visited[start] = 1 # 첫 시작점 방문처리 while stack: node = stack.pop() for i in linked[node]: # 인접한 노드 탐색 if visited[i] == visited[node]: # 인접한 곳이 서로 같은 숫자인 경우, 이분 그래프가 성립하지 .. 2022. 1. 19. [백준] 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. [프로그래머스] 튜플 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 원소들이 순서가 랜덤하게 있을 수 있으므로 길이 순서대로 정렬하였습니다. 또한 원소들을 집합으로 구분하여 현재 없는 원소를 쉽게 찾아내도록 사용하였습니다. 2) 풀이 코드 사용 언어 - Python def solution(s): answer = [] li = sorted(s[2:-2].split('},{'), key=lambda x: len(x)) # 양 끝의 중괄호 삭제, '},{' 기준으로 원소들 구분 후 원소의 개수순으로 정렬 for e in li: # 각 원소들 반복 num = set(e.split(',')) - set(answer) # 정답에 있는 현재 길이의 원소와 정답 원소들의 차집합을 구함 answer.append(num.pop()) #.. 2022. 1. 17. [프로그래머스] 타겟넘버 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 자릿수의 숫자가 더하기 아니면 빼기를 진행하여야 하므로 각 자리마다 두가지의 경우가 생깁니다. 첫번째 반복문에서 모든 경우의 수를 반복하고, 두번째 반복문에서 각 자릿수마다 확인하여 더하기와 빼기를 진행합니다. 2) 알고리즘 완전탐색 3) 풀이 코드 사용 언어 - Python def solution(numbers, target): answer = 0 # 정답의 개수 for i in range(1 2022. 1. 16. [백준] 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. [프로그래머스] 수식 최대화 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 입력이 하나의 문자열로 주어지므로 각 문자열을 반복하여 숫자들과 연산자들을 각각 다른 리스트에 정리하였습니다. 연산자의 우선순위를 바꿔서 임의로 선정이 가능하여, 순열을 통해 경우의 수를 모두 구했습니다. 숫자와 연산자 리스트를 같이 순환하며 우선순위가 높은 연산자를 만나면 계산 하여 새로 저장했습니다. 연산자의 종류가 세가지이므로 세번 반복하여 풀이를 진행하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python from itertools import permutations def solution(expression): answer = 0 # 정답 변수 op = ['*', '+', '-'] # 연산자 기호 _num_list = [] .. 2022. 1. 10. [프로그래머스] 후보키 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 후보키의 조합을 구해야하므로 조합을 구하는 모듈을 사용했습니다. 유일성과 최소성을 확인하기 위하여 집합을 사용하였습니다. 2) 알고리즘 조합 3) 풀이 코드 사용 언어 - Python from itertools import combinations # 조합 구하기 위한 모듈 임포트 def solution(relation): R = len(relation) # DB 행의 개수 C = len(relation[0]) # DB 열의 개수 cols = set() # 유일성과 최소성을 만족하는 후보키 목록 for i in range(1, C+1): # 열이 선택되는 개수 combs = list(combinations(range(C), i)) # 열이 i개 선택했을.. 2022. 1. 9. [백준] 14600 샤워실 바닥 깔기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 안쪽으로 영역을 나누어서 타일을 설치해야하므로 분할정복으로 접근했습니다. 2) 알고리즘 분할정복 3) 풀이 코드 사용 언어 - Python import sys def solution(r, c, k, area): # 시작 좌표, 제곱 수, 구역 global num if k 2022. 1. 8. 이전 1 ··· 10 11 12 13 14 15 다음
