본문 바로가기

알고리즘 온라인 저지/BOJ

 (34)
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를 이용하여 간단하게 문제를 풀고자 한다. 이때 일반적인 미로 찾기 입문 문제처럼 스택을 이용하지는 않는다. 그 이유는 스택을 이용할 경우 미로 최단경로를 찾기 위해서는 휴리스틱을 추가로 사용해야 하기 때문에 내용이 많아지기 때문이다. 휴리스틱을 위한 포스팅은 이후에 따로 하도록 하겠다. 위의 미로 지도와, 큐, 들어갈 노드를 이용해서 이..
BOJ 1238 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 특정 노드로 이동했다가 돌아와야 한다는 점을 추가해야 하는 최장/최단 거리 탐색 문제이다. 다익스트라 알고리즘의 동작에 대하여 잘 모른다면 [링크] 를 우선 참조하자 노드 A에서 출발했다 가정했을 때, 이미 방문한 노드 그룹에 대한 처리와, 이후에 필요할 다른 임의의 노드에서 A 노드로 왔다가 임의의 노드로 돌아가는 (= A에서 출발해서 임의의 노드로 이동하는) 값을 이용하기 위하여 아래와 같이 memo 변수를 추가로 이용했다. 그..
BOJ 1202번 보석 도둑 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 정답으로 출력할 값이 int의 영역을 벗어나는 것을 예측 못해서 시간을 조금 소비했던 문제였다. 문제 자체는 그리디 알고리즘의 정석에 가깝다고 생각된다. 문제에서 주어진 예시는 설명에 적합하지 않은 관계로 아래와 같이 임의로 만든 예시를 가지고 설명을 진행한다. 이 문제는 가방 1개당 가져갈 수 있는 보석이 1개로 1 대 1 매칭이 된다. 용량이 20 짜리 가방에 무게가 1짜리 보석을 넣어도 해당 가방..
BOJ 2014 소수의 곱 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제를 어렵게 생각하지 않는 것 이 중요한 문제다. 각 소수마다 계산해야 하는 대상이 달라질 수 있는데, 그 대상을 새롭게 탐색하지 않는 부분에 포인트를 맞추어 구현했다. 최초에 정답 확인용 리스트에 1을 넣은 채로 시작하도록 하자. 파란 사각형은 입력으로 주어진 소수들을 의미하고, 파란 사각형 밑에 붙을 흰색 작은 사각형은 각 소수의 연산 대상이라고 생각하면 된다. 자세한 내용은 아래에 기술한다. 각 소수 별로 다른 우선순위 큐 를 ..

티스토리툴바