이숭간 공부기록

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의 인자값으로 각 노드가 들어감 - 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다. - 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다. 단, 여기서 부모..

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) : 상..

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제유형 : 그리디, 정렬 문제풀이 회의가 겹치지 않으면서 최대수를 구해야하므로 끝나는시작이 빠를수록, 끝나는 시작이 같다면 시작하는 시간이 빠를수록 해당 회의를 선택하는것이 최대의 회의개수를 만들수 있다. 시작시간으로도 한번더 정렬해줘야 하는 이유는 시작시간과 종료시간이 같은 회의일경우 count를 해줘야하기 때문이다. 현재일의 시작시간이 이전일의 종료시간보다 크면 count를 증가시킨후, 종료시간을 현재일의 종료시간으로 갱신한다. 정답코드 import sys input = sys.stdin.readline n = int(i..