이숭간 공부기록

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..

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제유형 : 그래프, DFS/BFS 문제풀이 : 그래프에서 연결된 리스트 (덩어리)의 개수를 찾는문제이므로 DFS/BFS를 통해 그래프를 탐색한다. dfs함수는 시작노드에서부터 연결된 노드들로 재귀적으로 호출되며 더이상 방문할 노드가 없을때 리턴된다. 따라서 전체 노드를 순회하며 아직 방문 전일때, 해당 노드를 시작노드로 하여 DFS함수를 실행하면 ..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제유형 : BFS 문제풀이 주어진 2차원배열을 graph에 저장한다. 초기상태에서 1인 위치를 큐에넣고, BFS를 통해 인접노드들을 확인하며 0인경우(익지않은 토마토)일때만 1로 바꿔준다. 인접노드는 상하좌우로 움직인 4가지 노드이며, 조건을 통해 그래프 범위를 벗어나지 않도록 체크한다. 여기서는 -1일때는 어차피 아무것도 할수없으므로 신경쓰지 않아도 되고, 0인경우에는 1로 바꿈과 동시에 방..