알고리즘
[백준] 2213번 - 트리의 독립집합
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 💡 원리 트리의 정점에 가중치가 있으며, 독립집합을 찾는 문제이다. 문제를 잘 읽어보면 트리의 동적 프로그래밍을 사용하면 풀리는 문제인데, 이 문제는 더 나아가 출력으로 가장 큰 독립집합의 값의 정점을 찾아 출력을 해야한다. 우선 동적 프로그래밍을 사용해 가장 큰 독립집합을 찾아보자 트리의 형태이기 때문에 root=0 부터 차례대로 정점을 탐색할 수 있고, 동..
[백준] 15684번 - 사다리 조작
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 💡 원리 문제의 정답 비율을 보고 풀기에 무서웠던 문제였다. 하지만 문제를 잘 읽고, 잘 생각하면서 코드를 짜면 생각보다 쉽게 풀어지는 문제였다. 이 문제는 쉽게 주변에서 볼 수 있는 사다리 타기 게임과 같은 원리의 문제이다. 하지만 사다리 타기 게임과 다른 점은 두 가로선이 연속하면 안 되는 것에 있었다. ( 이 조건은 이 문제를 정말 쉽게 풀 수 있게 해주는 조건이였다.) 이 문제의 가장 중..
[백준] 14888번 - 연산자 끼워넣기
ps://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 처음에 연산자가 아닌 수들의 순서도 바뀔 수 있는줄 알고 푸는 방법을 생각해내는데 애를 먹었었다. 하지만 나중에 수들의 순서는 고정된 것을 알아채고, 연산자의 순서만 바뀐다는 것을 알고 해결방법을 쉽게 생각해낼 수 있었다. 만약 수들이 모여 있고, 이 수들의 모든 경우의 수를 구하고 싶다면 next_permutation을 사용해 구할 수 있다..
[백준] 9205번 - 맥주 마시면서 걸어가기 (카스텐라우프)
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발 www.acmicpc.net ✏️원리 Kastenlauf 카스텐라우프는 독일에서 주로 하는 술게임이라고 한다. 이 문제는 위 게임과 룰이 같으며, 맥주 20병을 담을 수 있는 박스를 들고 페스티벌까지 50m씩 맥주를 마시면서 맥주가 동이 안 날 때까지 마시면서 갈 수 있는지 없는지를 해결해야 하는 문제이다. 이 문제를 보고 나서 처음에 DFS로 풀어야지하며, DFS로 풀어보았다. 하지만 계속 시간초과가 나와, 계속 시간..
[백준] 12100번 - 2048(Easy)
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net https://play2048.co/ 2048 Join the numbers and get to the 2048 tile! Careful: this game is extremely addictive! play2048.co ✏️원리 예전에 2048게임을 많이 했었는데, 이렇게 알고리즘 문제로 풀게되니 신기했다. 우선 2048은 동서남북, 이렇게 4방향으로 블록을 움직일 ..
[백준] 17070번 - 파이프 옮기기 1
💡 깊이 우선 탐색 (DFS) 삼성 A형 기출문제라 해서 풀어봤는데, DFS로 손쉽게 풀 수 있는 알고리즘 문제였다. 먼저 파이프를 밀어 옮겨야하는 상황에서 파이프에 옮기는 방법은 가로 2가지, 세로 2가지, 대각선 3가지인데 DFS를 이용해 조건을 잘 맞추어 모든 상황을 고려해 만들어주면 된다. 가로인 경우 - (x,y+1), (x+1,y+1) 세로인 경우 - (x+1,y), (x+1,y+1) 대각선인 경우 - (x,y+1), (x+1,y), (x+1,y+1) 이때 주의할점은 옮겨야 할 곳이 1인 곳은 가지 못하도록 해줘야하는데 가로와 세로는 각각 (x+1, y)와 (x, y+1)만 고려해주면 되지만 대각선은 (x-1,y) (x,y-1) (x,y), 총 3가지를 고려해줘야 한다. ✏️ 구현 코드 #in..