Young

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 | 프로그래머스 programmers.co.kr 이번에는 카카오 코딩 테스트 4번째 문제 풀이 입니다. 이 문제는 'Trie' 자료구조를 사용하는 문제입니다. 문자열 알고리즘은 크게 KMP, Trie, Rabin-Karp, Aho-Corasick, Suffix Array 가 있습니다. Trie를 사용하는 문제는 알고리즘 대회나 코딩 테스트에서 흔히 볼 수 있는 문제는 아닙니다. 카카오 코테에서 이 문제는 두 번이나 나온걸 보면 좀 특이하긴 합니다. Trie 는 여러 문자열을 빠르게 찾을 수 있도록 저장하고 있는 자료구조 입니다. 어떤 문자열이 있나 찾을 때 아주 빠르게 찾을..

'재귀함수를 이용한 완전탐색의 기본에 대해서 (1)' 에서는 간단하게 숫자 조합을 고르는 방법에 대해서 알아 보았습니다. 사실 이것만 알면 그보다 좀 더 어려운 문제들 푸는 모든 준비는 끝났지만, 응용하는 방법을 알아보기로 합시다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 www.acmicpc.net 오늘 또한 완전탐색입니다. 지도가 주어졌을 때 최단거리는 보통 BFS로 구하게 됩니다. 하지만, 최대 10개가 주어지는 더러운 칸을 어떤..

https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2로 바꾸면 식이 성립한다. 9567 + 1085 ------ 10652 복면산 문제가 주어질 때, 답이 존재하는지 여부를 출력하시오. 단, 같은 문자는 같은 숫자에 대응되어야 www.acmicpc.net 오늘도 완전탐색입니다. 세 개의 문자열이 주어지면, 존재하는 각 알파벳에 0부터 9까지의 숫자를 분배해주고, 덧셈을 만족하는지 보면..

https://www.acmicpc.net/problem/17252 17252번: 삼삼한 수 첫째 줄에 2,147,483,647보다 작거나 같은 음이 아닌 정수 N이 입력된다. www.acmicpc.net 이 문제는 풀 수 있는 방법이 크게 두 가지가 있습니다. 1. 수학적 풀이 2. 완전탐색 수학적 풀이는 다음에 소개하기로 하고, 이번에는 완전탐색으로 푸는 방법을 소개하겠습니다. 아무래도 코딩 테스트에서 완전탐색이 자주 나오기 때문이죠. 약 3^21 정도면 2,147,483,647 을 넘어서게 됩니다. 그러므로 3^0부터 3^21 까지 1번 또는 0번 사용해서 만들 수 있는가를 알아내기 위한 완전탐색을 수행하면 시간복잡도는 O(2^N) 으로 최대 2^21 = 약1000000 으로 시간안에 충분히 가능합..

https://www.acmicpc.net/problem/17255 17255번: N으로 만들기 음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000) www.acmicpc.net 최대 8자리 숫자가 들어옵니다. 들어오는 숫자가 작아서 완전탐색으로 충분히 가능합니다. 시간복잡도는 O(N * 2^N) 입니다. 완전탐색은 BFS, DFS 아무거나 사용해도 됩니다. 이 코드에서는 DFS로 풀었습니다. 경로가 같은 것은 같은 경우의 수로 가정하는데, 이를 걸러내는 방법이 여러가지 있지만 각 경로를 string으로 이어 붙여서 마지막에 set 자료구조를 사용해서 걸러내면 됩니다. 예를 들어서 123이 들어온다면, 1 -> 12 -> 123 경로를 이어붙이면 112123 이 되고, 이를 set에 in..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 2019년 하반기 삼성 기출문제입니다. 이 문제에서 가장 어려운 점은 바로 '디자인'입니다. 도대체 이 윷놀이 판을 어떻게 디자인해야 하는가...? 처음 해본다면 굉장히 난해합니다. 1. 정사각 배열을 만들어 똑같이 그린다. 2. 원을 하나의 노드라고 생각하고, 그래프로 생각하여 디자인한다. 아무래도 directed graph로 생각하고 디자인하는게 훨씬 쉬워 보입니다. 다만, 파란색 노드에서 시작할 때, 다른 방향으로 가게끔 해주는 코드를 작성해주면 됩니다. 노드 갯수가 총 33개 정도(?) 되는 것 같네요. 뭐 이정도면..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출 www.acmicpc.net 딱 두가지 경우만 생각해보면 된다. 1. 전설의 명검없이 바로 공주가 있는 곳으로 간다. 2. 전설의 명검이 있는 곳으로 간..