Algorithm
[백준] 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방향으로 블록을 움직일 ..
[백준] 13900번 - 순서쌍의 곱의 합 (부분합)
이 문제를 보고, 무작정 Brute Force로 풀면 되지 않을까라고 생각했다. 하지만 시간 제한 부분에서 (추가 시간 없음)을 보고, 이렇게 쉽게 나올리 없다고 생각하며 다른 방법을 생각해보았다. 예전에 비스무리한 문제를 풀었던 기억이 있는데, 잘 기억이 나지 않았다. 이렇게 잘 기억이 나지 않을 때는 식을 써보면 기억이 나기도 하여, 노트를 이용해 식을 작성해보았다. 예제 입력 2으로 먼저 식을 나열하면, (1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4) 위와 같이 나오는데, 정리를 해보면 아래와 같이 나온다. (1*(2+3+4)) + (2*(3+4)) + (3*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..
프림 알고리즘 (Prim Algorithm)
👉 크루스칼 알고리즘과 같은 원리로 동작하는 또 다른 스패닝 트리 알고리즘이다. 💡 크루스칼 알고리즘이란? 참고 : https://withseungryu.tistory.com/70?category=753127 크루스칼 알고리즘 (Kruskal Algorithm) 👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 � withseungryu.tistory.com 프림 알고리즘과 크루스칼 알고리즘의 큰 차이는 진행 방식입니다. 크루스칼 알고리즘은 여기저기서 산발적으로 만들어진 트리의 조각들을 합쳐 스피닝 트리를 만드는 방법이고, 프림 알고리즘은 하나의 시작점으..
크루스칼 알고리즘 (Kruskal Algorithm)
👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘) 💡 MST란? 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제 크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다. 하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다. 👉 동작하는 과정 위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다. 이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고, 4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리..
Union-Find, Disjoint Set (유니온-파인드, 상호 배타적 집합)
☞ Union-Find 란? 상호 배타적인 부분 집합(Disjoint Set)들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 Union-Find에는 자료 구조에 명칭에 맞게 연산이 초기화(init), 합치기(union) 그리고 찾기(find)로 이루어져 있습니다. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화 합치기 연산 : 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합치는 연산 찾기 연산 : 어떤 원소가 주어질 때 이 원소가 속한 집합을 반환하는 연산 ☞ 상호 배타적 집합을 표현하는 방법은 2가지가 있는데, 첫번째는 배열입니다. 하지만 배열로 표현을 하면 합치기 연산에 드는 시간이 많이 걸리기 때문에 Union-Find 자료 구조 특성 상 효율적이지 못합니다. 그..