어흥

문제 링크: https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 1. 주의할 점 - 괄호에 대한 처리 - 문자열을 복원 v.s 길이만 구하기 2. 구현 - 문자열을 복원하지 않고 길이만 구해도 되므로, 길이만 구하여 메모리 또한 아낄 수 있도록 한다. 다만, 구현이 좀 더 복잡 할 수 있다 - Stack 2개를 이용하여 해결한다 #예시 234(10) - Len 스택에는 '(' 괄호가 나오기 전의 숫자를 제외하고 계산된 길이. 위의 예시에선 '..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 1. 주의할 점 - N≤10^5이므로 간선들의 정보를 나타내는 2차원 배열을 사용하지 않는다 2. 구현 - 가장 높은 등수는 1+ (해당 학생보다 잘 본 학생 수) - 가장 낮은 등수는 전체 학생수 - (해당 학생보다 못 본 학생 수) - Check[][2] 배열을 통해 각 Node를 방문했는지 검사한다([][0]: 정방..

문제 링크: https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 주의할 점 - 위상정렬로 접근한다 - 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피 2. 구현 - Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다 - Need[] 배열을 통해 필요한 총 물건의 수를 저장한다 - Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다..

문제 링크: https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 1. 주의할 점 - 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다 2. 구현 - Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다 - Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다 - 플로이드 와샬 알고리즘을 통해 Arr[][]..

문제 링크: 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..