본문 바로가기

전체 글

 (70)
BOJ 1389번 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 그래프의 탐색 문제이다. 너비 우선, 깊이 우선 둘 다 가능할 것 같지만 너비 우선 탐색의 구현이 더 간단하여 BFS를 사용하였다. 문제의 예시는 좌측과 같은 형태의 그래프로 표현 가능하다. 각 간선의 비용을 1이라 가정하고, N번 노드에서 출발하여 다른 노드들로 이동하는 비용의 합이 N번 노드의 케빈 베이컨 수 가 된다. BFS를 이용해 1번 노드의 케빈 베이컨 수 를 구해보자. 1번 노드에서 1번 노드로 이동하..
BOJ 7576 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전에 포스팅했던 미로 탐색 문제와 거의 동일한 문제이다. 큐 자료구조를 이용한 BFS를 한번 더 포스팅하고자 한다. 이번에는 날짜를 다루는 변수를 큐에 넣지 않고 진행한다. 위와 같은 2x2 행렬을 이용하며, 문제의 입력 예제 중 3번을 이용하고자 한다. 입력을 받을 때, 0의 개수를 카운팅 하여 현재 익지 않은 토마토의 개수를 가지고 있어야 -1 (= 모두 익히는 방법이 없음)을 처리할 수 있다. 이전 포스팅과 동일하게 큐를 이용하며, 왼쪽의..
BOJ 11054 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제를 풀기 위해서는 증가하는 부분 수열과, 감소하는 부분 수열을 각각 계산하여 합하는 것이 가장 간단해 보였다. 문제의 입력값을 위와 같이 표현할 것이다. 그림의 표는 순서대로 입력된 값들을 의미하며 표 위의 막대들은 해당 값을 가시성 좋게 높이로 표현한 것이다. 또한, 문제에서 명시된 바이토닉 부분 수열의 정의는 아래와 같다. 즉 어떤 수 k를 기준으로 좌우 방향으로 순감소 수열이라면 그 전체를 바이토닉 수열이라고 부른다는 것이다. 우리는 임의의 수열이 있을 때, 그중 일부만을 ..
BOJ 2042번 구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 본 문제는 세그먼트 트리라는 자료구조를 알고 있는가 없는가를 묻는 문제이다. 올바른 자료구조를 사용할 경우 별도의 조작 없이 바로 정답을 얻을 수 있기 때문에 세그먼트 트리의 튜토리얼 문제라고 볼 수 있다. 그렇기 때문에 트리의 개념과, 이진트리를 선행적으로 알고 있어야 한다. 추가로 배열을 이용해 이진트리를 구현했기 때문에 배열을 이용한 이진트리의 구현에 대해서도 선행적으로 알고 있으면 도움이 된다. ..
BOJ 16964 DFS 스페셜 저지 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 일반적인 DFS가 아닌, 주어진 입력이 DFS 탐색했을 때 올바른 입력인가? 를 판정하는 문제이다. 요 근래 들어가 가장 많은 시도 끝에 정답을 띄운 문제였던 것 같다. 결국 알고리즘 자체는 DFS라 간단하지만, 아이디어를 내는 것이 어려운 문제였다. 일반적으로 트리에 노드를 삽입할때, 특정한 기준을 둔다. 다시 말해 자식 노드 두 개 있을 때 더 작은 노드가 앞에오게 하거나 (= 오름차순 정렬) 더 큰 노드가 앞에 오게 하거나..
BOJ 1463 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 과거에 올린 BOJ 1697 숨바꼭질 과 동일한 문제이다. 다만 차이가 있다면 숨바꼭질은 +1, -1, *2 연산을 허용했다면 이번 문제는 -1, /2, /3 연산을 허용한다는 것만 다르다. 그래서 이번에는 숨바꼭질 문제와 반대로 목적지 ( = 1)에서 시작하여 역연산 (*2, *3, +1)을 하여 답을 찾아보기로 한다. 규칙은 아래와 같다. (규칙 A) 현재 도달 가능한 숫자를 큐에 저장한다. (규칙 B) 저장된 숫자를 하나씩 꺼내어 *2 / *3 / +1 연산을 해준다. (규칙 C) 규칙 B에 의해 연산된 결과에 해당하는 숫자가 기존에 탐색되지 않았다면, 해당 숫자에 현재..
BOJ 1339 단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 단어들의 합이 최대가 되어야 한다는 점 때문에 자칫 착각할 수 있지만, 문제 자체는 각 단어들에서 가장 많이 등장한 알파벳부터 9, 8, 7, ... 0 의 가중치를 주기만 하면 되는 간단한 문제이다. 하나의 단어에 대하여 문제를 풀 수 있다면 여러 개의 단어를 대상으로도 같은 해법으로 접근이 가능하다. 위와 같이, 단어 테이블과 알파벳 테이블을 이용하여 단어 한 개에 대하여 문제를 해결한 뒤, 여러 개의 단어에 상황에 적용해보자 아이디어를 간단하게 정리할..
BOJ 2178 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 찾기 문제이지만 최단거리를 구해야 하므로 가장 간단한 BFS를 이용하여 푼 문제이다. 오른쪽과 같이 문제에서 제시된 미로를 이용하며. 큐를 이용한 BFS를 이용하여 간단하게 문제를 풀고자 한다. 이때 일반적인 미로 찾기 입문 문제처럼 스택을 이용하지는 않는다. 그 이유는 스택을 이용할 경우 미로 최단경로를 찾기 위해서는 휴리스틱을 추가로 사용해야 하기 때문에 내용이 많아지기 때문이다. 휴리스틱을 위한 포스팅은 이후에 따로 하도록 하겠다. 위의 미로 지도와, 큐, 들어갈 노드를 이용해서 이..

티스토리툴바