어흥

문제 링크: https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 주의할 점 - 최단경로에 사용되는 간선인지 아닌지 구분이 필요하다 - 최단경로 알고리즘에 대해 알고 있어야 한다 2. 구현 - 모든 그래프의 경로를 알기 위해 Arr[][] 배열을 생성과 초기화한다 - 최단경로가 저장된 값을 Result[][] 배열에 저장한다 - Result[][] 배열에 입력된 간선들에 대한 정보를(중복 제외) 우선순위큐에 저장한다(가중치의 오름차순으로 정..

문제 링크: https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 1. 주의할 점 - 출력값은 오름차순으로 출력되어야 한다 - 총 의사전달시간의 최소가 아닌 의사전달시간의 최대값의 최소(전체가 아닌 각각) 2. 구현 - Arr[][] 배열과 Check[] 배열을 초기화한 이후, 값을 입력 받는다 - 플로이드와샬 알고리즘을 통해 Arr[][] 배열을 갱신한다 - 1~Node번까지의 참석자들을 모두 탐색하며 Check[] 값이 False라면 DFS(i..

문제 링크: https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 주의할 점 - 메모아이즈(DP) + 비트마스크를 통해 해결한다 - 순회 만족 조건은? 2. 구현 - 비용에 대한 정보를 Arr[][] 배열에 담는다 - Check[Cur][Val] 배열을 통해 Cur 도시에 도착할 때 방문했던 도시번호들의 합을 Val이라고 한다. 이 때, 비용의 최소값을 저장한다 - 순회가 된다면, 어떤 Node에서 시작해도..

문제 링크: https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. 주의할 점 - 특정 지점에 방문했을 때, 서로 다른 물건의 조합을 가지고 접근한 경우 어떻게 처리할 것인지 생각한다 2. 구현 - 위의 주의할 점의 예시로, (1,1)을 방문할 때 [0,1]번 물건을 가지고 접근했을 때와 [1,2]번 물건을 가지고 접근했을 때를 구분하기 위해 비트마스크를 이용한다(비트마스크 접근을 위한 추가 힌트: 최대 5개의 물건) - 집의 구조를 In..

문제 링크: https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 주의할 점 - 초기화 작업을 거친다 - 다익스트라나 플로이드와샬 알고리즘에 대해 알고 있으면 해결할 수 있다(Tree라서 DFS도 간단히 가능) import java.util.*; import java.lang.*; import java.io.*; class Main { static final int MAX = 987654321; static int node,query; public static void main (Strin..

문제 링크: https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - 출력 결과를 Long 타입으로 출력한다 - 계산하는 과정에서 Int타입을 벗어날 수 있다 2. 구현 - X+A = X|A 를 만족하려면, X를 비트로 바꿨을 때, 0에 해당하는 부분을 1로 채워주면 된다 - 이 과정에서 위의 식이 성립하는 K번째로 작은 수를 구하기 위해 K도 비트로 바꾼다 - 왼쪽부터 시작해서 X의 0에 해당하는 부분이 현재 K를 비트로 바꿨을때 1이라면 해당하는 만큼의 수를 더하고 0이라면 더하지 않는다 (아래 TC 참조) #1 X = 10 -..

문제 링크: https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net 1. 주의할 점 - 입출력 시간단축 필요 - STL인 BitSet을 이용 or Int[] 배열을 이용하여(32bit) 표현 2. 구현 - 비트셋을 이용하여 비트셋에 있으면 무시, 없으면 저장+출력을 진행한다 - 비트셋을 이용하지 않을 경우, Int 타입인 Arr[] 배열을 통해 입력받은 숫자를 32로 나눈다(..

문제 링크: https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 1. 주의할 점 - 비트마스크를 이용하여 문제를 해결한다 2. 구현 - 기억하고 있는 알파벳의 상태를 curKnow 변수에 저장한다. 초기에는 26가지 모두 알고 있으므로 curKnow = (1