문제 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://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 후보키 개념이 애매모호해서, 그것부터 정리하고 문제풀이를 시작했다. 문제의 핵심은 유일성보다는 최소성을 어떻게 판별할것인가, 였던거 같다. 최소성을 판별하기 위해서는 부분집합을 활용하면 된다. 만약 속성이 '학번' , '이름', '학년' 이라고 가정해보자. 이 때 '학번' 하나만으로도 후보키가 될 경우, '학번' 이 특정 집합의 부분집합이 되는 순간 최소성을 위반한다. '학번' ..

문제 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 알고리즘을 활용한다. 연결하려는 두 노드의 루트노드가 같다면 사이클이 존재한다는 것이다. 사이클이 발생하지 않을경우에만 비용값을 더해주고 ..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 dp 방식으로 생각해보면 '내가 위치한 계단을 어떻게 오느냐' 에 초점을 맞춰보면 된다. 내가 i번째 계단에 있다면 나는 1. i-1 번째 계단에서 왔거나 2. i-2 번째 계단에서 왔을것이다. 단 i-1번째 계단에서 왔다면, i-2번째계단을 밞고오진 않았을 것이다. (그렇게 되면 3개 연속 계단을 밞으니) 따라서 i-3 번째에서 왔을것이고 이를 활용하여 점화식을 세울 수 있다. D[i] = max..