이숭간 공부기록

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를 이용해서 상하좌우로 이동하는데, 이때 지도를 넘어가진..

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

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제유형 : 구현, 시뮬레이션 문제풀이 주사위굴리기 구현 - move함수 '뱀'문제랑 비슷하게 한가지부분만 좀 어려운걸 구현하면 나머지는 문제요구사항대로 구현하면 된다. '뱀'문제에서의 회전방향의 구현이 그랫듯이 이문제도 주사위를 굴려갈때 각 위치의 숫자를 바꿔주는 것이 중요했다. move()함수로 이동방향이 동서남북중 어디인지를 나타내는 dir..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제유형 : 구현(시뮬레이션) 삼성문제는 시뮬레이션문제가 많다. 그중에서도 BFS/DFS나 그래프(지도)에서 움직이는형태가 많다 문제풀이 : 문제의 요구사항을 차근차근 맞추서 충족시키면 풀 수 있다. 방향의 변화 회전의 방향은 시계방향('D')과 반시계방향('L')으로 나뉜다. 상(0) 우(1) 하(2) 좌(3) 라고 했을때 시계방향(D) : 상 - 우 - 하- 좌 - 상 순으로 바뀌고 (+1) 반시계방향(L) : 상..