본문 바로가기

Algorithm14

[백준]5052. 전화번호 목록 5052. 전화번호 목록 개요 - 이 문제는 전화번호의 접두어 유무를 판단하는 문제로 트라이 자료구조를 사용하는 대표적인 문제이다. - 트라이 자료구조를 구현하고, 다루는 방법을 안다면 간단히 해결할 수 있는 문제이다. 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록.. 2022. 3. 1.
[백준] 14425. 문자열 집합 14425.문자열 집합 개요 - 이 문제는 입력된 문자열의 포함 여부를 구분하는 문제로 두 가지 방법으로 접근해보았다. - 첫 번째는 트라이(접두사 트리) 자료구조로 해결하려 했고, 두 번째는 HashSet 자료구조로 해결하려 했다. ( 트라이 자료구조 게시글 - https://develop-grow.tistory.com/entry/자료-구조-트라이접두사-트리?category=957707 ) - map을 기반으로 트라이를 구현하여 문제를 풀었더니 시간 초과로 문제 해결에 실패했다. 배열을 기반으로 트라이를 구현하여 문제를 해결하였다. 두 가지 방식의 차이점은 시간복잡도와 메모리 공간 크기이다. 이는 마지막 후기에 작성해놓았다. 문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개.. 2022. 2. 27.
[백준] 2606.바이러스 2606.바이러스 개요 - 이 문제는 트리의 각 노드(문제에서는 컴퓨터라고 표현)간 연결되어 있는지 찾는 문제로 너비우선탐색, 깊이우선탐색 어떤 방식으로 풀어도 해결할 수 있다. - 솔루션은 너비우선탐색 방식으로 해결하여 포스팅했다. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네.. 2022. 2. 21.
[기본 개념] BFS(Breadth-First Search) BFS(Breadth-First Search) 개요 - 너비 우선 탐색의 기본 개념과 사용하는 상황, 구현 방식을 알아본다. 기본 개념 - 너비 우선 탐색은 루트 노드(임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다. - 기본 개념만으로는 이해하기 힘든 부분이 있으니 아래 탐색 과정을 보면서 이해하자. 탐색 과정 - 하기의 트리를 1번 노드(임의의 노드)부터 너비 우선 탐색하는 과정을 살펴보자. 1. 1번 노드를 탐색 대상으로 선정한다. 2. 1번 노드를 탐색하고, 1번과 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 3. 2,3,4번 노드를 탐색하고 2,3,4번 노드와 인접해 있는 노드들(다음 탐색 대상)을 조사한다. 4. 5,6,7 노드를 탐색하고 5,6,7번 노드와 인접해 .. 2022. 2. 12.

티스토리툴바