Baekjoon
-
[백준-1165,13502] 단어 퍼즐 (Trie,DFS,FTP)Baekjoon 2020. 5. 19. 14:22
*답을 구하는 해법을 기술 하였고 실제 제출시 통과되는 풀이는 아닙니다. *실제 제출시 통과되는 풀이로 업데이트 예정 문제 요약 대문자 알파벳이 하나씩 적혀있는 5x5의 보드와 단어 리스트 (사전)가 주어진다. 주어진 보드의 각 칸에서 8방향 탐색을 통해 사전에 있는 단어를 몇개 만들 수 있는지를 구하는 문제이다. 문제 풀이 문자열을 검색한다는 개념에서 Trie를 활용한 풀이를 기술한다. 다만 이 문제의 가장 큰 제약사항은 "소스 코드의 크기가 65536B를 넘을 수 없다"는 점이다. 제약사항을 봤을 때 이 문제를 풀기 위한 올바른 접근 방법은 코드안에 사전 데이터를 미리 넣어야 한다는 것이다. 주어진 사전 속의 단어의 개수는 24830개이고 이 텍스트 데이터들을 코드에 그대로 넣으면 이클립스 같..
-
[백준-11112] Eight Puzzle (Astar Algorithm)Baekjoon 2020. 5. 12. 14:32
문제 요약 8-Puzzle 게임을 푸는 문제이다. 3x3 보드판에 한칸의 빈공간, 나머지 칸에는 1~8 숫자가 무작위로 위치해 있다. 빈칸과 숫자의 자리를 바꿔 이동시키며 정답을 찾아가는 게임이다. 입력으로 주어지는 보드는 1부터 8사이의 숫자가 섞여있으며 #은 빈 공간을 나타낸다. 빈공간과 인접한 칸의 숫자와 자리를 바꿔보며 원하는 보드의 모양을 만들기 위한 최소의 이동 횟수를 구하면 된다. 문제 풀이 기본적으로 탐색 알고리즘을 통해 풀 수 있는 문제이다. 이 문제에서 제한된 시간은 1초이며 테스트케이스는 100개이다. 제한된 시간 내에 효율적인 탐색 방법으로 풀어야 하는 문제이며 본문에서는 Astar Algorithm을 활용한 풀이를 기술한다. Astar Algorithm은 미래에 가망 있는 값 ..
-
[백준 1422] 숫자의 신Baekjoon 2020. 4. 28. 00:41
문제 요약 입력으로 K개의 숫자가 주어진다. 이때 각 숫자의 범위는 1,000,000,000보다 작거나 같은 자연수이다. 이때 주어진 숫자들을 골라 앞, 뒤로 붙여서 만들 수 있는 숫자 중 가장 큰 숫자는 무엇인지 구하라. 단, 입력으로 주어진 K개의 숫자는 반드시 한 번씩 들어가야 하고, 여러 번 쓸 수 있다. 접근 과정 처음에 문제를 읽었을 때 문제 자체는 짧고 명료하기에 쉽게 이해했지만 구현에 대한 아이디어를 떠올리느라 매우 깊은 고민에 빠지게 됐다. 첫 번째로 든 생각 "그냥 큰 숫자만 앞에 가면 되는 거 아니야?" 반례 K=2일 때 1007, 7 이 주어졌다면 1007이 크다고 해서 1007+7 = 10077로 만든 건 정답이 될 수 없다. 7+1007을 하면 71007이 더 크기 때문이다. 해..