문제 https://www.acmicpc.net/status?user_id=whipbaek&problem_id=3190&from_mine=1 채점 현황 www.acmicpc.net 풀이 처음에 헷갈렸던거 1. 가장 좌측 상단은 [1, 1] 이다. [0, 0] 이 아니다. 2. 시간과 방향이 입력될 때 8 D, 10 D 이런식으로 들어오는데 시간초는 절대적인 시간을 의미한다. 8초가 끝난 후에 이후 추가적인 10초가 아니라 '시작 시간' 이후의 시간을 받는것이니 헷갈리지 말자. 풀이 처음에는 방향을 설정해줬다. L을 받으면 왼쪽으로 틀고, D를 받으면 오른쪽을 틀도록 dx, dy를 설정했다. 이후에는 사과의 위치와 뱀의 위치를 저장하는 2차원 배열을 각각 만들었다. * 생각해보니 이 두개의 정보는 한 배열..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 해당문제는 조합의 경우의 수를 구하면 바로 해결되는 문제이다. 위의 식을 고대로 구하면 답이 나온다. 단 팩토리얼은 DP로 미리 다 계산해둔다음 풀면 쉽게 풀 수 있다. 코드 d = [1] * 31 d[0] = 1 d[1] = 1 for i in range(2, 31): d[i] = d[i-1] * i t = int(input()) for _ in range(t): n, m = map(..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 https://www.youtube.com/watch?v=rhda6lR5kyQ&t=704&ab_channel=%EC%BD%94%EB%93%9C%EC%97%86%EB%8A%94%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D * 위 영상을 참고했음 코드 n, k = map(int, input..

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 완전탐색이 조금 곁들여진 구현문제이다. 우선 최대 5번을 움직여야하니 경우의 수를 모두 만들어주면 된다. 난 itertools 의 product를 사용해서 경우의 수를 만들었고, 각자 숫자와 방향을 매칭해서 생각했다. ( 0, ← ) , ( 1, ↑ ) , ( 2, → ) , ( 3, ↓ ) 이후에 숫자를 어떻게 합칠지 말지를 생각했는데, 행 단위로 생각했고..

문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 문제를 풀기전, 해당 문제의 x와 y값을 잘 참조하자. 해당 문제 풀이의 핵심은 시계방향으로 회전하고, 그 방향을 계속 저장해주는것이다. 우선 격자를 이동할 배열 순서를 → ↑ ← ↓ 순으로 저장한다. 0방향으로 시작하는 드래곤 세대들을 살펴보면 ※ 0세대 : → ※ 1세대 : → ↑ ※ 2세대 : → ↑ ← ↑ ※ 3세대 : → ↑ ← ↑ ← ↓ ← ↑ 순으..

문제 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 풀이 완전탐색 + Multisource BFS 문제이다. 여러개의 시작점을 모두 구한 후에, BFS를 모두 실행해본다음, 빈칸에 바이러스를 다 퍼트리는 경우, 최솟값을 구하면 된다. 빈칸에 모두 퍼졌는지는 초기에 빈칸의 개수를 구하고, BFS 실행 로직에 빈칸만큼 바이러스가 퍼진지 확인했다. 문제를 풀면서 이슈가 좀 있었는데 1. 시간초과 처음 완전탐색을 위해서 itertools.permutatio..

문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 나는 현재 위치 기준으로, 다음 변하는 값이 큰 값인지, 작은 값인지에 따라 분기를 나누었다. (만약 한 칸 차이가 아니라면 무조건 안되므로 바로 False!) 큰 경우를 살펴보면 예로, 배열은 [2,2,3,3] l은 2 라고 해보자. 2의 개수를 계속 카운트 하다가, 3이 나오면 경사로는 2에 설치해야한다. 따라서 2의 개수가 l개 이상인지 판단하면 된다. 만약 경사로를 설치할 수 있다면 현재값을 3으로 이..

문제 https://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 풀이 삼성 기출답게 시뮬레이션, 빡구현 문제다. 주사위의 절대적인 위치를 배열로 정해둔다. (난 문제에서 나온 숫자와 위치를 매칭했다.) 이후 동, 서, 남, 북 이동시에 갱신되는 로직을 각각 작성하면 된다. (이건 실제로 주사위 한 번 굴려보거나 그림 그려보면 된다.) 그리고 이동한 칸의 값을 보고 복사여부를 따져주면 된다...

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 bfs 기반 빡(?)구현 문제이다. bfs로 계속 탐색을 하면서 현재 물고기 크기에서 먹을 수 있는 물고기를 모두 찾아본다. 단 탐색시에 자신보다 큰 물고기를 지나갈 수 없고, 같은 크기의 물고기는 지나는 가되 먹을 물고기에 추가하지는 않는다. 그렇게 현 상황에서 먹을 수 있는 모든 물고기를 저장해둔 배열을 다중 조건으로 정렬해줘야한다. 1. 크기 2. 크기가 같다면 열 오름차순..

문제 https://www.acmicpc.net/status?user_id=whipbaek&problem_id=1197&from_mine=1 채점 현황 www.acmicpc.net 풀이 제목 그대로 최소스패닝트리(MST)를 만드는 문제다. MST를 만드는 방법으로는 크루스칼과 프림 알고리즘 두개가 있는데 나는 크루스칼을 활용하여 풀었다. 크루스칼은 edge들의 비용순으로 오름차순 한 후에, 하나씩 연결해보는 알고리즘이다. 연결하다가 사이클이 발견되면 그 edge는 뛰어넘고 다음 edge를 확인해보는 식으로 반복된다. 이 때 사이클을 감지하기 위하여 union find 알고리즘을 활용한다. 연결하려는 두 노드의 루트노드가 같다면 사이클이 존재한다는 것이다. 사이클이 발생하지 않을경우에만 비용값을 더해주고 ..