알고리즘 문제풀이/Python179 [프로그래머스] 길 찾기 게임 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어진 노드의 정보들을 이용하여 트리를 만들어내려 하였습니다. 그러나 트리를 만드는 과정에 다소 조건이 많았기에, 트리를 생성하지 않고 이진트리의 순회하는 방식의 특징을 이용하였습니다. 순회를 할때 현재 노드를 중심으로 하여 왼쪽 자식 노드와 오른쪽 자식 노드를 구하여 순회를 하였습니다. 2) 알고리즘 트리 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(10000) def solution(nodeinfo): answer = [[], []] # 전위 순회, 후위 순회 nodeinfo = list(sorted(enumerate(nodeinfo, start=1), key=lambda x: (x[1][1.. 2022. 2. 13. [백준] 13549 숨바꼭질 3 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수빈이가 동생의 위치로 이동하는데 걸리는 최소의 시간을 구해야 하므로 다익스트라를 이용하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] # 처음에 시작은 0초, 처음에 출발하는 수빈이 위치 while heap: if road[K] != -1: # 동생한테 도착했다면 종료 return node = heapq.heappop(heap) if 0 2022. 2. 12. [백준] 1701 Cubeditor 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 KMP 알고리즘으로 접근하여 주어진 문자열에서 가능한 패턴을 추출하여 2번 이상 포함되는 경우를 반환하도록 접근하였습니다. 그러나 제한시간을 초과하여 KMP 알고리즘을 이용할때 사용하는 접두사와 접미사가 일치하는 길이를 저장하는 테이블로 접근하였습니다. 이 테이블은 접두사와 접미사가 어느 길이로 일치하는지 저장하는 테이블로, 특정 패턴(접두사)이 문자열의 가장 뒤쪽(접미사)와 일치하므로 문장에 패턴이 두번 이상 나오게 되어 문제의 조건에 부합합니다. 그리하여 테이블의 값에서 가장 큰 값을 반환하도록 하였습니다. 2) 알고리즘 KMP 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') de.. 2022. 2. 11. [프로그래머스] 방금그곡 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 패턴이 여러 문자들 중 포함되는지 여부를 판별해야 하므로 KMP 알고리즘으로 접근하였습니다. 2) 알고리즘 KMP 3) 풀이 코드 사용 언어 - Python def solution(m, musicinfos): def separate(s): # 문자열 음을 리스트 형태로 나누어주는 함수 result = [] # 리스트로 변형된 음 for c in s: if c == '#': # 현재 인덱스가 # 이라면, 이전에 기록한 음에 # 이 붙어야하므로 result.append(f'{result.pop()}{c}') # 마지막 요소를 꺼낸 후 뒤에 붙여서 다시 추가 else: # 현재 문자가 # 이 아니라면 반환할 리스트에 항목 추가 result.append.. 2022. 2. 10. [백준] 16916 부분 문자열 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 단순한 완전탐색을 시도하려 했으나, 시간 초과가 우려되어 KMP 알고리즘을 학습 후 풀었습니다. 2) 알고리즘 KMP 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def make_table(pattern): j = 0 # 접두사 인덱스 for i in range(1, len(pattern)): if j > 0 and pattern[i] != pattern[j]: # 접두사 인덱스와 가장 마지막 문자가 일치하지 않으면, 접두사 인덱스 초기화 j = 0 if pattern[i] == pattern[j]: # 현재 접두사 인덱스와 가장 마지막 인덱스의 문자가 일치하면 j += 1.. 2022. 2. 9. [프로그래머스] 순위 검색 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 점수들을 찾는 쿼리문에서 - 기호가 존재하여, 특정 항목을 구분하지 않고 찾아오는 경우가 있습니다. 이를 위해 사용자들의 점수를 받을때, 조합을 이용하여 - 기호가 어느 위치에 들어가는지 모두 구해주었습니다. 그리하여 응시자 선택 사항을 키값으로 하는 딕셔너리에 점수들을 추가하였습니다. 정확성 테스트는 통과했으나, 효율성 테스트는 통과하지 못했습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python from itertools import combinations def solution(infos, query): answer = [] # 정답 리스트 people = {} # 선택한 항목별 점수를 저장할 딕셔너리 for info in inf.. 2022. 2. 8. [백준] 16120 PPAP 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 PPAP 문자가 있으면 P 로 계속해서 변환을 해준다면 PPAP 문자인지 알 수 있습니다. 단순히 문자열에서 PPAP 가 발견되면 P 로 변환을 해주게 되면 시간초과가 발생 할 수 있다고 판단하여 스택과 큐를 이용하여 풀었습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') S = deque(sys.stdin.readline().rstrip()) # 입력 받은 문자 answer = [] # 한글자씩 쌓을 문자 리스트 while S: # 입력 받은 문자가 아직 남아있으면 반복 answer.append(S.po.. 2022. 2. 6. [백준] 1254 팰린드롬 만들기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 팰린드롬은 특정 위치를 기준으로 오른쪽 문자들이 앞뒤가 뒤바뀌어도 같으면 왼쪽의 문자열 길이를 뒤에 붙이면 팰린드롬이 만들어진다는 특성을 이용하여 접근하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') S = list(sys.stdin.readline().strip()) # 입력 받은 문자열 idx = 0 # 오른쪽을 확인할 기준 인덱스 while True: if S[idx:] == S[idx:][::-1]: # 인덱스를 기준으로 오른쪽의 문자들만 앞뒤로 뒤집었을때 팰린드롬인지 확인 break idx += 1 # 팰린드롬이 아니면 인덱스 증가 print(.. 2022. 2. 5. [백준] 4358 생태학 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 나무의 종의 개수와 나무의 종별 개수를 파악해야하므로 딕셔너리를 이용하여 데이터를 저장하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') tree = {} # key: 나무 이름, value: 나무의 개수 for name in sys.stdin.read().strip().split('\n'): # 모든 입력들 tree[name] = tree.get(name, 0) + 1 # 딕셔너리 변수에 나무가 없으면 0으로 초기화 하고 + 1, 이미 있으면 1 증가 total = sum(tree.values()) # 나무의 총 개수 for k in sorted(tre.. 2022. 2. 4. [백준] 16398 행성 연결 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소 스패닝 트리 문제로 크루스칼 알고리즘으로 접근하였습니다. 2) 알고리즘 크루스칼 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(100000) sys.stdin = open('input.txt') def find(n): # 정점이 속한 집단의 대표를 찾음 if n != s[n]: s[n] = find(s[n]) return s[n] def union(x, y): # 정점 x와 y를 합침 s[find(x)] = find(y) def solution(): global answer edge_cnt, idx = 0, 0 # 정점이 모두 연결되었는지 확인을 위한 변수, 간선의 인덱스 while edge.. 2022. 2. 3. [백준] 1197 최소 스패닝 트리 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소 스패닝 트리 문제로 크루스칼 알고리즘으로 접근했습니다. 2) 알고리즘 크루스칼 3) 풀이 코드 사용 언어 - Python def find_set(x): # 정점 x 의 최상단 정점을 찾음 if x != s[x]: s[x] = find_set(s[x]) return s[x] def union(x, y): # 두개의 집합을 서로 합침 s[find_set(y)] = find_set(x) def kruskal(): # 크루스칼 알고리즘 global answer edge_cnt, idx = 0, 0 # 모두 연결이 되었는지 확인을 위한 변수, 간선 집합의 인덱스 번호 while edge_cnt != V-1: # 정점-1 개 만큼 연결되어 있지 않으면 x .. 2022. 2. 2. [프로그래머스] 뉴스 클러스터링 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문자열을 특정 길이로 모두 자른 후 알파벳인 경우에만 판별을 하여야하므로 영문자를 판별하는 isalpha 메서드를 사용하였습니다. 단순히 집합을 이용하면 중복되는 문자들은 1개만 남게 되는데, 문제에서는 중복을 유지시켜야 했기 때문에 딕셔너리를 이용하여 중복을 유지시켰습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python def solution(str1, str2): one, two = {}, {} # 문자열들을 2글자씩 자른 갯수를 카운트하는 딕셔너리 변수 intersection = 0 # 교집합의 개수 union = 0 # 합집합의 개수 for i in range(1, len(str1)): # 첫번째 문자열의 두글자가 문자열로만 .. 2022. 2. 1. 이전 1 ··· 8 9 10 11 12 13 14 15 다음
