-
[알고리즘 문제 풀이][유니온파인드] 백준 20040번 - 사이클 게임자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 7. 8. 21:07
백준 20040번 사이클 게임입니다. (Union Find 혹은 Disjoint Set) - 문제 설명: https://www.acmicpc.net/problem/20040 - 문제 풀이: 본 문제는 일반적으로 유니온 파인드를 이용하는 문제입니다. 각 정점마다 연결된 부모를 관리해주는데, 서로 다른 그룹에 속한 정점을 합치게 되면 (Union) 각 그룹의 최상위 부모를 찾아서 (Find) 두 부모 중 하나를 부모로 만들어줍니다. 유니온 파인드 개념에 대해 알지 못한다면 아래 개념을 참고하시거나, 간단한 유니온 파인드 기초문제부터 풀어보시는 것을 추천드립니다. * 유니온 파인드란? https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html * 유니..
-
기차놀이 게임 만들기 (snake game)SW개발 2022. 5. 12. 01:12
댄싱 기차놀이 게임 javascript 로 개발하였고, 윈도우용 실행파일로 만들기 위해 electron 으로 빌드하였다. snake game 을 javascript 로 개발한 교육용 소스 코드가 있어서, 이를 기반으로 개발하였다. ios 앱 빌드를 하고 싶었지만, 애플 스토어에 올리지 않고 외부 배포 가능한 방법을 찾지 못하여서 만들지 못하였다. (p5.js 는 사용하지 않았다. image 및 audio 코드는 직접 넣어도 될 것 같아서 굳이 외부 라이브러리가 필요 없었다) 게임 플레이 해보기: https://by1994.github.io/dance-snake-game/ github repository: https://github.com/BY1994/dance-snake-game 개발에 참고한 자료들 [..
-
[알고리즘 문제 풀이][재귀] 백준 11729번 - 하노이 탑 이동 순서 / 1914 번 - 하노이 탑자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 3. 1. 15:48
백준 11729번 하노이 탑 이동 순서 / 1914번 하노이 탑 문제입니다. (재귀) - 문제 설명: https://www.acmicpc.net/problem/11729 - 문제 풀이: 백준 단계별로 풀어보기의 '재귀' 연습 문제입니다. (https://www.acmicpc.net/step/19) 하노이 탑은 시작점에 있는 원판들을 도착점으로 옮기는 것인데, 직접 이동시켜보면 최소 이동 횟수가 2^n - 1 개가 나오는 것을 알 수 있습니다. 왜 그렇게 나오는지 재귀적으로 생각해보면 다음과 같습니다. 원판이 3개 있는 경우를 살펴보겠습니다. 그러면 맨 마지막 3번째 칸이 맨 끝 도착지점에 가기 위해서는 반드시 위의 2개의 원판이 가운데 지점에 놓여야합니다. 그래야 3번째 원판을 도착 지점에 먼저 깔고 작..
-
[알고리즘 문제 풀이][세그먼트트리] 백준 3392번 - 화성 지도자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 28. 17:40
백준 3392번 화성 지도 문제입니다. (세그먼트 트리 & 스위핑) - 문제 설명: https://www.acmicpc.net/problem/3392 - 문제 풀이: 본 문제는 다른 블로그들의 풀이를 참고하여 풀었기 때문에, 기존 풀이 방식과 동일합니다. 본 문제는 세그먼트 트리를 공부하기 위해 풀게 되었는데, 세그먼트 트리의 기초 개념만 알면 풀 수 있었던 문제들과 달리, 본 문제는 어느 부분에 세그먼트 트리를 적용해야할 지 어려운 문제였습니다. 일반적인 풀이는 들어온 입력들을 정렬을 하고, 쭉 스캔을 하면서 스캔한 범위에 사각형의 일부가 들어있으면 그걸 다 합하는 방식입니다. 이때 스캔한 범위에 사각형 선이 들어있는지 아닌지를 세그먼트 트리로 관리합니다. 들어온 입력을 보면 아래와 같습니다. 사각형 ..
-
[알고리즘 문제 풀이][DP] Leetcode 264번 - Ugly Number II자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 19. 19:46
릿코드 264번 Ugly Number 2 문제입니다. (DP) - 문제 설명: https://leetcode.com/problems/ugly-number-ii/ - 문제 풀이: 본 문제는 대부분의 풀이가 DP 로 나오지만, Heap 자료구조를 이용해서도 풀 수 있습니다. (1) Heap 을 이용한 풀이 min Heap 을 이용하면 현재 숫자 중에 가장 작은 숫자를 매번 꺼낼 때마다 알 수 있기 때문에, 여기에 *2, *3, *5 한 값을 다시 Heap 자료구조 안에 넣어서 꺼내주면 됩니다. (2) DP 풀이 DP 풀이를 보기 위해 문제의 예제를 보면 아래와 같습니다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 처음에는 1로 시작합니다. 그 다음에 1에서 2 곱한 값은 2, 3 곱한 값은 3,..
-
[알고리즘 문제 풀이][기하학] 백준 3053번 - 택시 기하학자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 15. 00:21
백준 3053번 택시 기하학 문제입니다. (기하학 - 도형의 넓이) - 문제 설명: https://www.acmicpc.net/problem/3053 - 문제 풀이: 첫번째 출력은 원의 넓이를 출력하는 것입니다. 원의 넓이는 𝜋𝑟² 이므로 어렵지 않을 것입니다. 두번째는 택시기하학에서 같은 점들로 이루어지는 도형의 넓이를 구해야합니다. 택시 기하학에서 거리는 문제에서 주어졌듯이, |x1-x2| + |y1-y2| 로 구해야합니다. (x1과 x2 차이의 절대값, y1과 y2 차이의 절대값) 예를 들어, 중간 지점인 (x1,y1) = (0,0)을 기준으로 삼고, 길이가 10이라면 아래와 같은 점들이 모두 길이가 10이 나온다는 것을 알 수 있습니다. 여기서 x2 값을 한 칸 줄이고, y2 값을 한 칸 늘여도 ..
-
[알고리즘 문제 풀이][완전탐색] 백준 12784번 - 인하니카 공화국자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 13. 16:17
백준 12784번 인하니카 공화국 문제입니다. (완전탐색 - DFS) - 문제 설명: https://www.acmicpc.net/problem/12784 - 문제 풀이: 본 문제는 맨 끝 부분 노드 (리프 노드)와 가장 상위에 존재하는 1번 노드 (루트 노드) 사이의 연결을 끊는 문제입니다. 가장 최소로 다이너마이트 개수를 사용하고 싶다고 했으므로, 자식부터 부모로 올라가면서 자신의 아래 자식 사이 길을 끊는 게 이득인지 자신과 부모 사이 길을 끊는게 이득인지 판단하면 됩니다. 이 문제는 어떤 노드가 자식 노드인지 예제에서 주어지지 않아서 BFS를 하기 위해서는 한 번 for 문을 돌면서 찾아야한다는 귀찮음이 있어 대부분 DFS 로 구현한 코드가 많습니다. - 코드: (1) DFS 코드 (출처) http..
-
[알고리즘 문제 풀이][기하학] 백준 1002번 - 터렛자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 2. 12. 20:05
백준 1002번 터렛 문제입니다. (기하학 - 원의 교점의 개수) - 문제 설명: https://www.acmicpc.net/problem/1002 - 문제 풀이: 본 문제는 현재 위치, 적까지의 거리가 주어집니다. 그런데 한 명의 정보가 아니라 2명의 정보가 주어집니다. 문제를 풀기 위해서는 두 명의 정보가 동시에 가리키는 위치를 찾아야합니다. 하나의 거리가 r1 으로 주어졌을 때 가능한 좌표는 r1 만큼 떨어진 모든 곳이므로 원을 하나 그리게 됩니다. 또 다른 한명이 가리키는 거리가 r2 로 주어지면 가능한 좌표는 r2 만큼 떨어진 원형이 됩니다. 두 명이 동시에 가리키는 좌표는 겹치는 한 곳일 수도 있고, 원 두 개가 겹치는 경우를 생각하면 2 곳일 수도 있습니다. 원의 교점의 개수를 구하기 위해 ..