컴공생 일상 블로그 컴공생 일상 블로그

https://www.acmicpc.net/problem/1516 알고리즘다이나믹 프로그래밍 / 그래프 이론 / 위상 정렬 / 방향 비순환 그래프 설명예 ~ 전에 풀려다가 못 풀었었는데, 오랫만에 보니까 금방 풀었다.문제 내용부터 '나 위상 정렬' 이라고 말하고 있기 때문에, 그냥 위상 정렬 후 소요 시간만 잘 계산하여 주면 된다. [각 작업에 대한 최소 소요 시간] = [입력 간선으로 들어오는 노드들 중, 가장 늦게 끝나는(최대 소요 시간)] + [해당 노드의 작업 시간]위상 정렬  코드#include #include #include #include using namespace std;int N;int cost[501];int result[501]; //각 건물을 짓는데 필요한 시간int in[5..

https://www.acmicpc.net/problem/30689 알고리즘그래프 이론 / 그래프 탐색 / 깊이 우선 탐색 / 함수형 그래프설명이전에 풀었던 텀 프로젝트 문제와 비슷한 느낌이 난다.재귀를 통하여 구현해당 유형은 익숙하지가 않아 구현 실수가 많은 것 같다.이번 차례에 방문한 칸과 이전에 방문했던 칸을 체크하는 두 개의 vistied 배열을 사용하여 미로 내의 사이클을 찾는 문제만약 사이클을 발견하게 되면, 사이클을 이루는 칸 중 가장 비용이 작은 칸을 정답에 더해준다.코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;string arr[200..

문제 - 아리스, 청소합니다 Easy 버전 https://www.acmicpc.net/problem/31404 31404번: 아리스, 청소합니다! (Easy) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 64)$ 두 번째 줄에 아리스의 처음 위치를 나타내는 $R, C, D$가 주어집니다. 아리스의 좌표는 $(R,C)$이고, 위쪽을 기준으로 시계 www.acmicpc.net - 아리스, 청소합니다 Hard 버전 (크기 빼고, Easy와 완전 동일) https://www.acmicpc.net/problem/31399 31399번: 아리스, 청소합니다! (Hard) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 1\..

알고리즘 : 깊이 우선 탐색, check 배열을 두 개를 돌리면서 사이클을 검사해야하는 문제(위상정렬로도 가능) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 알고리즘 : DFS, BFS, 구현(섬의 높이를 어떻게 구해나갈지 생각하기가 힘들었음) https://www.acmicpc.net/problem/1109 1109번: 섬 첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다...

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW 를 사용하여 두 선분의 교차 관계를 판정하는 문제이다. 행렬 연산 시, 오버플로우를 간과해서 계속 틀렸다. ㅇㅅㅇ... - AB 선분, CD 선분 간의 교차 판정 R1과 R2가 모두 0 인 경우 : 서로 직선에 위치한 관계, x와 y에 대한 겹치는지 판정 R1과 R2의 곱이 음수인 경우 : 교차 int R1 = ( A, B, C 에 대한 CCW) * ( A, B, D 에 대한 CCW); int R2 = (C, D, A 에 대한 CCW) * (C, D..

Counter Clock Wise 점 A, B, C가 있을 때 3개의 점 A, B, C를 차례로 이은 직선의 모양을 알고자 할 때 유용한 기하 알고리즘이다. 세 점에 대해 다음의 3 가지 모양이 존재할 수 있다. 귀찮으니까 코드로 보자. AB와 BC 벡터를 구하고, 벡터를 Cross (외적) 연산하면 세 점 A, B, C의 관계를 알 수 있다. 반시계 방향 : 음수 시계 방향 : 양수 직선 : 0 #include using namespace std; struct xy { int y, x; }; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); xy A, B, C; cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C...

각 구간에 대해 특정 해를 항상 가지고 있는 트리. 자료구조로 생각하고 풀이하면 편하다. 각 구간 ~ 에 대해 최소값/최대값/합/곱 ... 을 가지는 트리 - 구간 합 (기본) https://www.acmicpc.net/problem/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 - 최대 최소 값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을..

https://www.acmicpc.net/problem/30826 30826번: 그 긴 수 팰린드롬 수는 앞에서 읽어도, 뒤에서 읽어도 같은 수를 말한다. 예를 들어, $7$, $88$, $14641$은 팰린드롬 수지만 $201$, $329$, $4700$ 등은 팰린드롬 수가 아니다. 상윤이는 팰린드롬 수 중 양의 정수면 www.acmicpc.net Ad Hoc 문제, 저번의 거울 숫자 문제와 비슷한가? 싶어서 건드려 보았는데, 그냥 각 경우를 고려해서 잘 짜주면 된다. - 문제 요약 팰린드롬 수를 순차적으로 계속 붙여나간 수에서 K 번 째 위치한 수를 찾아주면 된다. Ex. 12345678911223344556677 ... - 각 자리 수 마다 팰린드롬 수를 만들 수 있는 경우의 수 한자리 수의 경우..