알고리즘
-
BOJ) 집합 (11723 번)알고리즘/백준 2021. 1. 21. 18:53
집합 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 조건 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all:..
-
BOJ) 알고스팟 (1261 번)알고리즘/백준 2021. 1. 21. 18:22
알고스팟 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 벽이 존재하는 미로에서 처음 위치 (0,0)를 시작으로 (n-1,m-1)까지 도착해야한다. 이 때, 최소한으로 벽을 부시면서 경로를 찾는 문제다. 최소 + 경로 => 다익스트라를 이용하면 되겠다고 판단했다. 풀이 풀이는 간단하다. 일반적인 다익스트라를 구현하는 것 처럼 우선순위 큐를 활용해서 풀었다. 우선순위는 벽을 가장 적게 허문 순서대로 정렬했고, 이동하는 곳이 벽인 경우에는 +1을, 벽이 아닌 경우에는 +0을 해주며 길을..
-
BOJ) 녹색 옷 입은 애가 젤다지? (4485 번)알고리즘/백준 2021. 1. 19. 00:33
녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라를 알고, 적절하게 이용할 줄 아는가?를 물어보는 문제였다. 좌측 상단에서 우측 하단으로 이동하면서 돈을 가장 적게 뺏겨야하는 문제다. 처음에는 dp로 간단하게 풀 수 있겠다고 생각하고 코드를 작성했지만, 불규칙적으로 왔다갔다하는 경우가 있어서 다익스트라를 추가해줬다. 출발 지점을 우선순위 큐에 담아두고, 상하좌우를 돌면서 돈을 가장 적게 뺏기는 경우들을 저장하면서 큐에 넣어주었다. 이동하면서, 가장 적게 ..
-
BOJ) 트리의 지름 (1967 번)알고리즘/백준 2021. 1. 19. 00:25
트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이진 트리인줄 알고 시간을 조금 낭비했다. 왜 틀렸는지 잘 모르겠어서 게시판 글을 읽다가, 이진 트리가 아닌 케이스를 보고 해결했다. 풀이 풀이 방법은 간단하다. 각 tree의 연결 정보를 ArrayList에 담아두고 (n이 최대 10,000가 되는데, 배열로는 메모리 초과가 발생할 것임) dp라고 선언한 배열을 통해 각 노드에서 자식 노드의 최대 weight를 메모이제이션 해주었다. 그리고 답을 찾을 때는 우선순위 큐를 통해, ..
-
BOJ) 트리 순회 (1991 번)알고리즘/백준 2021. 1. 19. 00:18
트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이진 트리에 대한 개념을 알고 있다면 어렵지 않은 문제였다. 다만, 트리의 입력 정보가 포화 이진 트리인지, 완전 이진 트리인지, 정 이진 트리인지 보장해주지 않는다. (트리에 대한 개념 설명은 이전 자료구조의 트리 포스팅을 참고) 그래서, 해당 노드의 값에 따라 정보를 입력해주어야 한다는게 핵심이었던 것 같다. 위의 입력 문제를 해결하기 위해서 append라는 메소드를 만들었다. node의 vertex 값이 일치하는 node를 찾아 left, ..
-
BOJ) 뱀 (3190번)알고리즘/백준 2021. 1. 19. 00:03
뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 시뮬레이션 문제로 기억하는 사람이 있을지 모르지만, 피자를 먹으면 뱀의 꼬리가 늘어나는 게임이 있었다. 딱, 그 문제를 구현하는 문제였다. 아무튼, 행과 열을 오랜만에 이용하다보니 이에 대한 개념의 혼동으로 문제를 틀렸었다. 행은 가로에 대한 정보, 열은 세로에 대한 정보다. 따라서, 행은 y축의 index를 가지고 열은 x축의 index를 갖게된다. 풀이 문제의 조건에 머리가 뱀의 몸에 닿거나 벽에 닿으면 종료된다. 벽에 대한 정보를 저장해주려고 맵의 크기를 N+..
-
BOJ) 최소 스패닝 트리 (1197 번)알고리즘/백준 2021. 1. 7. 16:36
최소 스패닝 트리 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리 최소 신장 트리라고도 하며, Minimum Spanning Tree(MST) 로 많이 들어 봤을 것이다. MST는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소가 되는 트리이다. 즉, 최소 가중치를 가지며 그래프의 모든 정점을 연결하는 방법이다. 이 때, cycle이 생겨서는 안된다. 이 문제는 Prim과 Kruskal 알고리즘 두 개로 풀어봤다. ..
-
BOJ) 골드바흐의 추측 (9020 번)알고리즘/백준 2021. 1. 7. 16:18
골드바흐의 추측 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 소수는 에라토네스의 체를 이용하면 수월하게 소수를 구할 수 있다. 에라토네스의 체의 개념을 다시 환기하기 위해 작성한다. 추가적으로, 이 문제에서 출력 부분에 String.format을 이용해서 출력하는 방법과 띄워쓰기와 new line을 append 해주며 출력하는 방법을 이용해봤는데, 메모리와 속도 측면..