https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 키보드 바꾼 기념으로 오랜만에 문제를 풀어보았다. 틀린 문제로 나와있어서 다시 보니 간단한 문제였다. 주어진 10x10 칸에서 1인 곳을 색종이 좌상단을 붙힌다고 가정하고 하나씩 붙혀보면서 되면 다음칸으로 넘어가고, 붙힐 수 있는 게 없으면 탐색을 종료하는 백트래킹으로 풀 수 있다. 붙힐 수 있는 지 여부는 5개를 다 쓰거나, 칸이 넘어가거나, 0이 있거나, 다른 색종이로 붙혔을 경우이다..
https://www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net 아호 코라식 개념에 대해 공부해볼 수 있는 문제였습니다. 아호 코라식이란, KMP 확장 버전으로, 길이 N인 문자열과 길이 M1, M2, .., 인 문자열 간의 매칭을 O(N+M1+M2+...) 로 진행합니다. 즉, KMP는 1대1 매칭이라면 아호 코라식은 1대다 매칭 알고리즘입니다. (참고 : https://ansohxxn.github.io/algorithm/ahocorasick/) 먼저..
https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net KMP로 가볍게 해결할 수 있는 문제였습니다. 첫 번째로 제시되는 문자열이 찾고자 하는 단어, 두 번째로 제시되는 문자열이 기준이 되는 단어입니다. 두 번째 문자열을 2개 이어 붙힌 상황에서 첫 번째 문자열이 등장하는 횟수를 체크하면 됩니다. 다만 제시되었을 때부터 0번째부터 일치하는 경우, n번째에서 또다시 일치할 수 있으므로 이러한 경우는 제외시켜줍니다. 코드는 다음과 같습니다. #incl..
https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 주어진 문자열 집합에 대해 접두사인지 아닌지를 판별하는 문제입니다. 이를 판별하기 위해 trie 자료구조를 이용하였습니다. (코드 참고 : https://rebro.kr/86) Trie는 문자열의 character 단위로 노드를 생성하여 트리 구조를 이용해 탐색을 진행하는 방식입니다. char 단위로 노드를 생성..
https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 1부터 N까지 수에 대해 가장 긴 증가하는 부분 수열 길이가 M, 가장 긴 감소하는 부분 수열 길이가 K가 되도록 수열을 만드는 문제입니다. M*K 만큼 0으로 초기화된 배열에 K 간격으로 1부터 M까지 수를 넣고, 역순으로 나머지 수 중 큰 수를 차례로 넣게 되면 M, K 조건을 모두 만족하게 됩니다. 예를 들어, 10, 5, 4와 같은 경우 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 로 이루어진 배열이 있고 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 10 9 8 5 0 0 0 1 0 0 0 2 0 0..