알고리즘 문제풀이210 [백준] 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. [백준] 15686 치킨 배달 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 치킨집을 기준으로 하여 각 치킨집에서 집까지 치킨 거리를 모두 구하여 2차원 배열로 저장하도록 했습니다. 치킨집을 최대한 M개 모두 사용하는것이 도시의 치킨 거리를 가장 작게 만들 수 있으므로, M개 모두 선택했을때의 조합을 구하였습니다. 미리 구해둔 2차원 배열을 이용해, 각 집과 치킨집의 최소 거리를 찾아서 도시의 치킨거리의 최솟값을 구했습니다. 2) 알고리즘 브루트포스 3) 풀이 코드 사용 언어 - Python import sys from itertools import combinations sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 도시의 크기, 최.. 2022. 1. 31. [백준] 3190 뱀 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기 뱀의 몸을 좌표값으로 저장하여 DFS 탐색을 이용하는 방식으로 접근하였습니다. 그러나 뱀이 방향전환을 하면 얼굴만 방향 전환이 아닌 몸 전체가 방향을 전환하여 원치않는 결과가 나타났습니다. 뱀의 몸은 움직이지 않고, 머리와 꼬리 부분만 삭제와 추가를 컨트롤 하면 된다는 사실을 파악 후 큐를 이용한 구현으로 접근하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): snake = deque([(1, 1)]) # 뱀의 몸이 있는 위치 direction = 1 # 뱀의 진행 방향.. 2022. 1. 30. [백준] 18222 투에-모스 문자열 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 과정이 반복될수록 2의 제곱만큼 자릿수가 증가하는 규칙이 있어 초기 몇번째 값을 토글하여야 하는지 찾는 방식으로 접근했습니다. 2) 알고리즘 분할정복 3) 풀이 코드 사용 언어 - Python import sys import math sys.stdin = open('input.txt') K = int(sys.stdin.readline()) # 찾아야하는 자릿수 patterns = '0110' # 가장 앞의 4자리 sign = 0 # 반전 여부 while K >= 4: # 4자리 이상이면 반복 if sign: # 반전 여부 토글 sign -= 1 else: sign += 1 n = int(math.log2(K)) # 현재 자릿수보다 작거나 같은 2의 제.. 2022. 1. 29. [백준] 1963 소수 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 에라토스테네스의 체를 이용하여 소수를 구하였고, 여러 테스트 케이스마다 소수를 구하지 않도록 전역에서 필요한 소수들을 모두 구한 후 테스트케이스의 정답을 찾아나갔습니다. 각 자릿수 변경을 BFS 탐색을 이용하였는데, 반복문을 이용하여 각 자릿수를 변경해서 탐색을 진행하였습니다. 2) 알고리즘 에라토스테네스의 체 BFS 3) 풀이 코드 사용 언어 - Python import sys import math from collections import deque sys.stdin = open('input.txt') def solution(n): q = deque([n]) visited[n] = 0 # 시작 숫자는 0번 바꿔서 돌아오므로 0으로 지정 while .. 2022. 1. 28. 이전 1 ··· 9 10 11 12 13 14 15 ··· 18 다음
