알고리즘
-
BOJ 1019 책 페이지알고리즘/수학 2022. 7. 27. 09:22
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 간만에 머리좀 굴릴만한 문제를 풀었다. 1 ~ N 까지의 숫자들에 0 ~ 9 의 숫자가 각각 몇번씩 등장하는지 계산하는 문제이다. 당연히 1부터 N까지 하나하나 확인할 수 없도록 만들어놓았다. 그러면 규칙을 찾아야 할텐데.. 규칙을 찾을때는 역시 값이 작은 부분에서 손으로 노가다를 해보면 된다. 두자리수를 가지고 대충 감을 잡고, 세자리수에 적용을 해봐서 수정을 해가면서 식을 찾으면 된다. 아니 왜 세자리수인가요?? -> 가운데자리수 가 등장하는 제일 작은 숫자이..
-
BOJ 10875 뱀알고리즘/구현 2022. 7. 25. 10:49
https://www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 문제는 단순하다. 지나온 정점을 다시 지나가려 하거나, 격자판 밖으로 나가면 죽는다!! 그런데.. 격자판의 크기가.. 2억 * 2억 이다. vis배열을 당연히 사용할 수 없다. 나의 굳어버린 머리는 vis배열 없이는 도저히 해결할 수 없을 것 같았다.. 지나간 곳만 저장하는 sparse table을 이용해볼까 했는데.. 모든 정점을 지나가면?? 결국 vis배열을 사용한 것과 같아서..
-
BOJ 2243 사탕상자알고리즘/세그먼트 트리 2021. 11. 29. 08:37
https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net solved의 class 6에 속해있는 문제이다. 생각보다 금방 풀려서 난이도 기여를 해볼까 했는데 스탠다드였다. 플레5 치고는 쉽게 풀리는 문제이니 도전해보면 좋을 듯 하다. 문제를 딱 읽어보면 이분탐색이라는 느낌이 확 온다. 현재 보유하고 있는 사탕중 n번째로 맛있는 사탕을 꺼내면 되기 때문이다. 하지만 문제는 보유하고 있는 사탕의 현황이 계속 바뀐다. 따라서 사탕의..
-
BOJ 6549 히스토그램에서 가장 큰 직사각형알고리즘/세그먼트 트리 2021. 11. 24. 23:53
소마 코테 이후로 거의 8달 가까이 놓고있던 알고리즘 문제풀이를 다시 시작했다. 기억을 되살리기 위해서 템플릿을 보지 않고 기억에 의존해서 코드작성을 했는데, 생각보다 많은것을 아직 기억하고 있어서 다행이다. https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이 문제는 사실 군복무 전인 2018년 쯤부터 알고 있던 문제였으나, 접근방법을 몰라서 손도 대지 않고 있던 문제였다. 이후에도 몇번..
-
BOJ 1395 스위치알고리즘/세그먼트 트리 2021. 3. 22. 10:31
www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지 프로퍼게이션을 공부한지 한달 조금 안되었다. 구간합을 구하는 것에 더해서 구간 업데이트까지 가능하다고?? 정말 대단한 알고리즘이다. 하여간 이걸 연습해야 하는데.. 레이지 프로퍼게이션에는 오일러 경로 테크닉이 자주 따라오는 거 같다. 이건 모르는거니 필요없는 것중에 연습을 좀 하고 있는데 굉장히 멋있는 문제인것 같아서 풀어봤다. 보통 레이지프로퍼게이션 입문은 구간합..
-
BOJ 7812 중앙 트리알고리즘/트리 2021. 3. 18. 20:55
www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 굉장히 재밌는 문제같아서 언젠간 풀어보려 했는데 이번에 풀게 되었다. 그냥 모든점에서 다익스트라를 돌리고 싶은 생각이 드는데, 생각해보면 그래프라 다익말고 dfs로도 최단거리가 나온다. 그런데 dfs 시간복잡도가 O(v)라서 v개의 정점에서 모두 dfs를 한번씩 돌려보면 O(v^2) = 시간초과 이다. 당연히 다른 방법이 필요하다. 이런 스타일의 문제는 대부분 dfs를 활용하면서, 인접한 ..
-
BOJ 14570 나무 위의 구슬알고리즘/트리 2021. 3. 18. 08:48
www.acmicpc.net/problem/14570 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net 이것도 처음 봤을 때는 못풀었다. 아니, 각 상황에 따라서 구슬이 내려가는 위치가 다른데, k가 10^18이라고? 분할정복도 아니고, 트리dp인가?? 하다가 못풀었던 문제인데 이제보니 이렇게 쉬울수가 없다... 규칙을 잘 생각해 보면 답이 나온다. 각 노드에서 구슬은 왼쪽 또는 오른쪽을 선택한다. 이 규칙에 의해서, 모든 상황에서 자식의 구슬개수는 1. 양쪽 자식의 자식의 구슬개수가 동일하거나 2. 왼쪽..
-
BOJ 2250 트리의 높이와 너비알고리즘/트리 2021. 3. 17. 19:01
www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제를 본 지는 좀 되었는데, 그당시에 뭔소린지 모르겠어서 못 풀었던 문제이다. 이번에 한번 더 보았는데, 너무 쉬운 문제였다. 왼쪽의 숫자는 노드의 깊이이고, 아래의 숫자는 inorder탐색을 했을때의 방문순서이다!! 따라서 이 문제는 그냥 노드의 깊이마다 inorder탐색을 제일 처음 만난 친구와 제일 늦게 만난 친구의 탐색순서의 차이를 출력하면 되는 문제이다. #include using ..