# 문자열을 찾을때 사용하는 알고리즘이 여러가지 있는데, 대표적으로 KMP, 라빈카프, 보이어-무어, BruteForce, Trie등이 있다. 전체 문자열 길이를 N, 찾고자하는 패턴길이를 M이라 하면 BruteForce는 O(NM) / KMP는 O(N) + 전처리 / 보이어-무어는 O(N/M), 최악 O(N) / 라빈카프는 O(N)이다. # 이번에 소개할 자료구조는 Trie(트라이)라고 하는 자료구조인데, 우선 Trie라는 말은 retrieval(탐색)에서 따온 말이라고 한다. 트라이는 트리구조를 사용해서 문자열을 저장하는데, 시간복잡도가 가장 긴 문자열의 길이를 L이라 했을때 O(L)밖에 걸리지 않는다. # 우선 'fire', 'firefox', 'frodo', 'frost', 'fry'를 저장했을 ..
https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net # Trie(트라이) 자료구조로 푸는 문제이다. 1. Trie클래스를 선언한다. 1-1. insert메소드: 입력받은 먹이들(food배열)을 반복문으로 돌면서 cur_node의 key에 먹이가 없다면 cur_node[현재먹이] = {}로 만들어주고, cur_node의 key에 먹이가 존재한다면 cur_node = cur_node[string]으로 다음 먹이를 가리키도록 한다. 먹이의..
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net # 2021상반기 삼성SW 기출문제이다. # 청소년 상어와 마찬가지로 '삼성'스러운 문제이다. 단순구현, 시뮬레이션으로 쉽게 풀수 있다. 1. 처음 비바라기 마법을 시전하면 구름이 (N-2, 0), (N-1, 0), (N-2, 1), (N-1, 1)에 생기고 d방향으로 s만큼 이동한다. 그 뒤 1 ~ 5단계까지 이동명령을 따르는 것을 구현하고 새로운 구름 cloud를 return해준다. 2..
https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 8주차 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 1. 두개의 명함을 비교할때 나올 수 있는 케이스는 2가지 밖에 없다. A B A B C D 와 D C 두가지밖에 없다. 첫번째에서 A B를 뒤집으면 두번째 케이스와 같아지기 때문이다. 2. 결국 이 두가지 케이스를 a, b에 넣어주고 a의 명함넓이가 b 명함넓이보다 작으면 answer = a, 반대면 answer = b를 해주면서 answer값을 계속 갱신해준다. 3...
https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net # 1차원 누적합 문제이다. 1. 수열 num을 입력받은 뒤, 비내림차순으로 정렬해준다. 2. prefix_sum에 수들의 누적합을 구해서 append해준다. 3. Q만큼 질문의 답을 출력해준다. L R = B[L] + B[L+1] + .. + B[R-1] + B[R] 이므로 prefix_sum[R] - prefix_sum[L-1]을 출력하면 된다. import sys input = sys.stdin.readline N, Q = map(int,input().split()) num = li..
https://www.acmicpc.net/problem/16571 16571번: 알파 틱택토 현재까지 진행된 틱택토 게임 보드가 띄어쓰기로 구분되어 3줄에 걸쳐 주어진다. 0은 빈칸, 1은 X, 2는 O를 의미한다. 단, 항상 X가 선공이다. 그리고 이미 게임이 종료된 상태는 입력으로 주어지 www.acmicpc.net # 우리가 알고있는 3x3 틱택토 게임이다. import sys sys.setrecursionlimit(10**6) first, second = 0, 0 blank = [] m = [list(map(int,input().split())) for _ in range(3)] # 이미 1이 놓여진 칸과 2가 놓여진 칸, 0이 놓여진 칸을 세준다. for i in range(3): for j ..
https://www.acmicpc.net/problem/15998 15998번: 카카오머니 만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면 www.acmicpc.net # 2018 카카오 코드 페스티벌문제이다. # 문제자체는 구현문제라 어렵지 않은데, 예외처리가 까다로웠다 import sys input = sys.stdin.readline def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) N = int(input()) M = -1 minb = 10000000000000000..
https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net # C++ STL에는 next_permutation 메소드가 있지만, java나 Python에는 존재하지 않아 직접 구현을 해주었다. # https://hanil0623.tistory.com/2
모르는 사이에 조금씩 조금씩..
