달리는 개발자

백준 검색 결과

해당 글 78건

[BOJ 1011번] (Math) Fly me to the Alpha Centauri (C++)

Fly me to the Alpha Centauri (Gold 5) 문제 전체 문제 보기 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 접근법 이 문제는 정답의 규칙을 발견하면 간단한 수학 연산 몇 가지로 정답을 구할 수 있다. 규칙을 찾기 위해서 아래의 표를 살펴보자. 이 표를 살펴보면 두 가지 규칙을 찾을 수 있다. 항상 거리가 1,4,9,16 제곱수 이후 에서 이동 횟수가 1 증가하는 규칙을 볼 수 있다. 제곱수에서 증가한 후, 4 에서는 2회, 9 이후에는..

Algorithms/Math 2021. 8. 9. 13:11

[BOJ 5670] (Trie) 휴대폰 자판(C++)

휴대폰 자판(Platinum 4) 문제 전체 문제 보기 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 접근법 이 문제는 정렬을 활용해서 풀 수도 있고, 트라이를 활용해서도 풀 수 있다. 트라이 문제들 중에서는 이렇게 정렬 풀 수 있는 경우가 많은 것 같다. 필자는 이번 문제를 트라이로 풀었다. 트라이는 문자열의 접두어를 활용하는 문제 해결에 특화된 자료구조이다. 이번 문제에서도 자동 입력이라고 표현된 기능은 결국 중복된 접두어를 입력해주는 기능이기 때문에 트라이를 풀이했을 때 효율이 좋다고 판단했다. 자료구조 선..

Algorithms/Trie 2021. 8. 7. 16:28

[BOJ 14425번] (Hash) 문자열 집합 (C++)

문자열 집합 (실버 III) 문제 전체 문제 보기 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 접근법 해당 문제는 집합 S에 포함될 N개의 문자열들을 모두 해시 테이블에 저장한 뒤, 그 뒤에 주어지는 M개의 문자열을 해시 테이블에 탐색하여 해결하는 간단한 문제이다. (중복되는 문자열은 없다.) 해시 테이블에 삽입 및 탐색을 하는 시간 복잡도는 \(O(1)\)이기 때문에 전체 시간 복잡도는 \(O(n)\)이며 공간 복잡는 문자열 개수만큼 공간이 필요하기 때문에 마찬가지로 \(O..

Algorithms/Hash 2021. 8. 6. 18:18

[BOJ 14725] (Trie) 개미굴 (C++)

개미굴(골드 II) 문제 전체 문제 보기 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 접근법 트라이 자료구조를 이해하기 위해서 풀어본 문제이다. 트라이에 기본적인 설명은 이 글을 참고하자. 일반적으로 트라이라 하면 접두사를 검색하거나 단어를 검색하기 위해서 많이 사용된다. 그런데 이 문제에서는 하나의 노드에 하나의 단어가 들어가는 구조로 변형하여 사용한다는 특징이 있다. 자식 노드 개수에 제한이 없기 때문에 자식 노드의 포인터들을 배열처럼 정적인 공간에 담을 수는 없다. 그리고 여러 자식 노드..

Algorithms/Trie 2021. 8. 4. 23:40