알고리즘/BOJ
-
[BOJ 9250, C++] 문자열 판별 집합알고리즘/BOJ 2022. 9. 4. 22:42
https://www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net suffix array가 남았긴한데, 대표적인 문자열 알고리즘인 KMP, Trie, Aho-Corasick을 모두 배웠다. 아호코라식은 Trie 와 KMP를 섞은 일대다 패턴매칭 알고리즘이라고 한다. 결국엔 이것도 Trie를 사용하기 때문에 눈에 익으면 입력값 제한을 확인하여 유형을 찾을만한 알고리즘이라고 생각된다. 1. 문제 풀이 시간복잡도를 계산해보면 각 문자열마다 최대 10,000이고..
-
[BOJ 5670, C++] 휴대폰 자판알고리즘/BOJ 2022. 8. 25. 17:47
https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조를 공부했는데, 다른 블로그에 나와있는 문자열 트리 그림을 확인해보면 코드 이해가 KMP보다 쉽습니다. 근데 소멸자 쓰는 건 자료구조 수업 이후에 처음이라 정신 나갈 뻔했네요. 1. 문제 풀이 문자열을 탐색한다는 내용과 문자열이 겹치면 자동으로 완성한다라는 내용을 통해 트라이 자료구조를 사용해야 한다는 것을 알 수 있습니다. 그리고 트라이 문제를 캐치할 수 있는 제일 큰 핵심은 똑같은 문..
-
[BOJ 4354, C++] 문자열 제곱알고리즘/BOJ 2022. 8. 15. 21:30
https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 이런 상황일 때 실패함수를 사용하는 것이다를 잘 보여준 문제 1. 풀이 문제를 잘 읽어보면 S = A^n으로 어떤 문자열 S는 어떤 문자열 A를 n개를 이어 붙인 것이므로 aaaaaab, abaaaaa, aabbaaaa 같은 이런 문자열들은 저 문자열 그대로 A가 되어 S = A^1이 되는 것을 알 수 있습니다. 만약 S가 A의 알파벳을 순서대로 계속 붙인 경우..
-
[BOJ 8394, C++] 악수알고리즘/BOJ 2022. 8. 9. 12:34
https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 1. 문제 증명 예시가 4만 나와있는데, n = 1 ~ 3일 때도 확인해보면 피보나치 수열의 점화식이 나옵니다. arr[i] = arr[i-1] + arr[i-2] 피보나치 수열 점화식을 증명하는 방법은 생각보다 간단합니다. 회의에 참석한 사람 N명이 있고, 이미 우리가 1명부터 N-1명일 때까지의 경우의 수를 모두 구했다고 가정해보겠습니다. 이때 N-1명일 때의 경우의 수는 dp[N-1]입니다. N번째 사람이 추가되면 경우의 수가 2가지로 나뉘게 됩니다. 1) N번째 사람이 악수를 하지 않는 경우 이 경..
-
[BOJ 9167, Python 3] 도발 봇알고리즘/BOJ 2022. 5. 7. 03:55
https://www.acmicpc.net/problem/9167 9167번: 도발 봇 중세 기사 시대에, 사악한 조롱에 대항하는 정신력, 즉 '멘탈'은 아주 중요한 것이었다. 킹 현우는 자신의 노예들이 약한 멘탈을 갖기를 바라지 않았다. 그래서 자신의 엄청난 코딩 능력으로 트 www.acmicpc.net 풀이 지문에 나온대로 구현을 하면 됩니다. 1) 모든 것을 딕셔너리에 저장하고 시뮬레이션 돌리기 (재귀 O) 2) taunt, sentence, ..., past-rel은 함수로 구현하고, 나머지는 딕셔너리에 저장하기 (재귀 X) 풀이는 위처럼 크게 두 가지로 나뉠 것 같구요. 저는 두 가지 방법 모두로 풀었습니다.. 2번 풀이 같은 경우엔 jinhan814님 블로그에서 보고 풀었습니다. 계속 틀렸습니..
-
[BOJ 2424, Python 3] 부산의 해적알고리즘/BOJ 2021. 10. 26. 17:41
https://www.acmicpc.net/problem/2424 2424번: 부산의 해적 첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 구성되어 있는데, .은 바다이고, I는 섬이고, V는 해적의 위치이고, Y는 현재 수아의 위치이고, T www.acmicpc.net 해적이 언제 해당 지역을 볼 수 있는지 빠르게 확인하는 아이디어 때문에 난이도가 높은 것 같은데 코드양만 많지 의외로 쉽습니다. 풀이 수아가 움직일 때, 해적은 가만히 있거나, 움직이는 것을 선택할 수 있는 상태에서 해적의 움직임과 상관없이 수아가 보물을 얻을 수 있을지 구하라는 문제입니다. 해적의 움직임과 상관이 없으려면 해적은 최단시간안에 모든 지역을 볼 수 있어도 수아가 보물을..
-
[BOJ 23288, Python 3] 주사위 굴리기 2알고리즘/BOJ 2021. 10. 25. 19:48
https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 이번에 나온 삼성 SW 역량테스트 문제입니다. 풀이 먼저 점수를 저장할 배열을 만들어주고, 플러드 필을 이용하여 본문에 나온대로 각 칸마다 B와 C를 곱한 값을 점수 배열에 저장하면 됩니다. 이 부분은 쉬우니까 넘어가겠습니다. 문제는 주사위를 굴리는 것입니다. 이것은 전개도 그림을 사용하여 설명하겠습니다. 처음 전개도가 위와 같이 있을 때, 설명하기 쉬운 남쪽과 북쪽으로 이동하는..
-
[BOJ 23240, Python 3] Colorful Tower of Hanoi알고리즘/BOJ 2021. 10. 13. 21:03
https://www.acmicpc.net/problem/23240 23240번: Colorful Tower of Hanoi 입력은 표준입력을 사용한다. 첫 번째 줄에는 정수 $m$ ($1 \le m \le 25$)이 주어진다. 여기서, $m$은 가장 큰 디스크의 지름을 나타낸다. 이어지는 $m$ 줄에서, $i$ ($1 \le i \le m$) 번째 줄에는 하나의 영 www.acmicpc.net ICPC 2021 예선전에 나온 문제이다. 내가 맡아서 풀은 문제인데 대회 당시 분명 풀이가 맞지만 다른 예외사항을 찾지 못한 것 같아서 맞왜틀이 나와 결국 풀지 못한채로 끝났다. 지금 다시 풀어보니까 예외 사항 하나를 찾아서 풀었음 대회에서 풀었으면 등수가 거의 (현재 등수) / 2 수준으로 뛰어 올랐을텐데 참..