이숭간 공부기록

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제유형 : 브루트포스 문제풀이 : 조합을 이용한 완전탐색 nCn//2를 통해 팀을 반으로 나눌수있는 모든 경우를 구한다. 각각의 경우에서 다시 n//2C2를 통해 2명씩 시너지를 구해서 팀의 능력치를 구한다. 팀을 반으로 나눌수있는 모든 경우에 대해 팀의 능력치를 구했다면, 매칭되는 반대팀의 능력치와의 차이를 구해서 최소를 출력. 매칭되는 팀은 조합을 모두 구한후에 반으로 나누고 뒤엣부분을 거꾸로 뒤집으면 순서대로 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제유형 : 다이나믹 프로그래밍 문제풀이 : 1. 큰 문제를 작은문제로 쪼개서 생각해내는것이 필요 2번째 집을 파란색으로 색칠할때의 최솟값? -> 1번째집을 min(빨간색으로 색칠, 초록색으로 색칠) + 2번째집을 파란색으로 색칠할때의 비용 그렇다면 3번째 집을 빨간색으로 색칠할때의 최솟값? -> 2번째집을 min(파란색으로 색칠, 초록색으로 색칠) --> 위에서 구했네?? ..

한달동안 알고리즘문제에 손도 안댔더니.. 다 까먹어버린것같다.. 큰일났다.. DP (Dynamic Programming)이란? 큰 쿤제를 작은문제로 나누어 푸는것 동적 기억하기 프로그래밍 이라고 이해하는편이 좋겠다. DP와 분할정복의 차이 작은문제가 중복이 일어나는가 안일어나는가 분할정복 : 큰 문제를 작은문제로 나누어 푸는것은 맞지만, 작은문제들에서 반복이 없다!! DP : 작은문문제들이 반복되는것 (답이 바뀌지 않는) DP 적용방법 모든 작은문제는 한.번.만 푼다. -> 한번 구한 답을 어딘가 저장해놓는다. 이후에 다시 반복되는 작은문제가 나타나면 이미 구한답을 그대로 이용한다. DP의 조건 아래와 같은 조건을 만족하는 경우에 다이나믹 프로그래밍 풀이를 적용할수 있다. DP문제는 이 문제가 DP로 푸..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제유형 : 그래프탐색 (DFS & BFS), 브루트포스 문제풀이 : 전체 로직은 다음과 같다. 주어진 연구소의 빈 공간 중 3개의 벽을 선택한다. By itertools의 combination 조합라이브러리를 이용해 빈공간중에서 3개를 선택해서 배열에 저장하고, 이 배열을 돌면서 아래 2,3번 과정을 반복한다. 바이러스를 퍼뜨린다. By DFS (or BFS) DFS를 이용해서 상하좌우로 이동하는데, 이때 지도를 넘어가진..

www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제유형 : 브루트포스, 백트래킹 문제풀이 N의 범위가 최대 20이므로 완전탐색으로 모든 부분집합을 다 구해도 2^20승 (1,048,576)이므로 전체 부분집합을 다 구하고 조건에 맞는지 확인하는 완전탐색을 이용해도 됨 (파이썬에서 1초에 대략 2천만번의 연산이 가능하므로) 여러 풀이방법이 있음 (재귀, 멱집합 등등) 나는 원소의개수가 1부터n까지 증가하도록 조합을 사용하여..

본 글은 동빈나 2021 이코테 _ 8. 기타그래프 이론을 정리한 글입니다! 서로소 집합 자료구조 _ Union-Find 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조(=합치기 찾기 자료구조)는 두종류의 연산을 지원한다. 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - Union의 인자값으로 각 노드가 들어감 - 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다. - 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다. 단, 여기서 부모..