알고리즘/백준
-
BOJ) 달려라 홍준 (1306 번)알고리즘/백준 2021. 1. 26. 19:11
달려라 홍준 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 슬라이딩 윈도를 공부하기 위해 푼 문제였다. 슬라이딩 윈도는 주로 두 개의 네트워크 호스트간의 패킷의 흐름을 제어하기 위한 방법으로 사용된다. 고정된 크기의 윈도우가 전체 범위에서 움직이는 방식이다. 배열로 된 예시를 통해 이해하는게 더 수월했다. 위와 같은 배열에서 3의 크기로 전체를 탐색하는 경우 사용한다고 생각하면 편하다. 여러 블로그를 찾아봤는데, 슬라이딩 윈도의 핵심은 이전 값에 대해 중복되는 부분을 재사용한다는 것이..
-
BOJ) 암호코드 (2011 번)알고리즘/백준 2021. 1. 26. 18:54
암호코드 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제의 조건이 많이 주어지지 않아서, 예외 케이스를 많이 찾아야했다. 우선, 문제를 살펴보면 문자를 숫자로 암호화하는데, A=1, Z=26으로 암호화를 한다. 이 암호화된 숫자로부터 나올 수 있는 암호의 경우의 수를 구하는 문제다. 암호를 만들 수 없는 경우는 0을 출력한다는 조건도 있다. 먼저, 입력받을 때 부터 예외 케이스를 검증해주었다. 0으로 시작하는 경우, 연속으로 0이 들어오는 경우, 입력한 문자열이 빈 문자열인 경우, 숫자가 아닌 문자열이 들어오는 경우를 먼..
-
BOJ) 생물학자 (3116 번)알고리즘/백준 2021. 1. 21. 19:12
생물학자 3116번: 생물학자 첫째 줄에 박테리아의 수 N(1 ≤ N ≤ 5,000)이 주어진다.다음 N개의 줄에는 세 개의 정수 X, Y, D (-1,000,000 ≤ X,Y ≤ 1,000,000), (1 ≤ D ≤ 8) 가 주어진다. X와 Y는 박테리아의 시작 좌표이며, D는 방향이 www.acmicpc.net 수학 문제라고 느껴졌다. 박테리아의 위치가 주어지고, 방향이 주어진다. 아래의 방향에 따라서, 매 초 일정하게 이동을 할 때, 박테리아 여러 마리가 같은 칸에 제일 많이 있을 때가 언제인지, 그리고 그 때 몇 마리가 같은 칸에 있었는지 구하는 문제였다. 또한, X값은 왼쪽에서 오른쪽으로 갈 수록 증가하며, Y값은 위로 갈수록 증가한다는 조건이 있다. 즉, 1번은 매초 X값이 -1씩, Y값이 +..
-
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를 메모이제이션 해주었다. 그리고 답을 찾을 때는 우선순위 큐를 통해, ..