세그먼트 트리, Segment Tree ❓ 세그먼트 트리, Segment Tree 세그먼트(Segment)는 영어 뜻 자체로는 분할, 단편, 구분 등의 의미를 가진다. 이는 특정 구간 내 데이터에 대한 연산 또는 쿼리를 빠르게 구할 수 있는 트리이다. 보통 특정 구간 합, 최솟값, 최댓값, 평균값 등을 구할 때 활용한다. [시간 복잡도] 데이터 변경 : O(logN) 연산 : O(logN) 데이터 변경할 때마다 연산하기 M번 : O((logN + logN) * M) = O(MlogN) 선형 탐색을 이용한 구간 합 구하기 ‘특정 구간의 합을 구해라’는 말을 보면 가장 단순하게 생각할 수 있는 방법은 바로 선형 탐색이다. 다음과 같은 배열 {1, 2, 3, 4, 5}에서 2번 구간부터 4번 구간까지의 합을 ..

17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 읽기 처음에 DFS로 풀었는데 어김없이 시간초과.. 처음부터 시간초과가 나지 않을까 생각하긴 했는데, 최대 1000개의 집이 각각 2번씩 선택지가 있으니까 2^1000쯤 되려나? 싶다. (시간 계산 하고 풀자 ㅠㅠ) 어떻게 하지? 하다가 아 DP구나 싶었다. 최소 비용.. 넘치는 시간.. DP는 문제를 보고 이게 DP인지 파악하는 게 제일 힘들다던데 맞는 것 같다. 감을 잃지 말자. 문제 풀기 첫 번째 집에 칠한 색이 각각 R, ..

2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문제 읽기 일단 문제를 처음 읽고서는 BFS로 풀었었다. 하지만 거의 바로 메모리 초과가 났었고! 맵의 크기는 작지만 k의 존재와 중복 방문이 가능하기 때문에 BFS 수행 시 큐가 터져버리는 것이었다. (어쩐지 골드3인데 너무 쉽게 풀려서 이상했다.) 그래서 DFS로 접근했다. 단순 DFS를 처음에 했는데, 아무래도 중복 방문이 가능하다보니 이번엔 시간 초과가 났었다. 질문 게시판을 조금 뒤져서 메모제이션을 사용한다는 방식을..

1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 읽기 처음에 문제를 읽고 풀었을 때는 dfs로 풀었었다. 그런데 3퍼센트 쯤에 시간 초과가 나와서 그냥 다른 방법을 생각해야겠구나 싶었다. 최단 거리니까 다음과 같은 세 가지 방법이 있었다. 다익스트라 벨만포드 플로이드워샬 각각은 사용하는 경우가 다양한데, 처음엔 다익스트라? 생각했다가 시작 지점이 정해져 있지 않기 때문에 다익스트라를 하려면 여러 번 돌려야만 했다. 그래서 모든 지점에서 다른 모든 지점까지의 최단 거리를 ..

16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 읽기 처음에 딱 읽었을 때는 DFS가 생각났다. 그래서 dfs로 짜다가.. 생각해보니 벽을 피해서 움직여야 하고, 8방으로 움직여야 한다. 맵의 크기가 매우 작긴 하지만, 벽을 피해서 이동하는게 최우선이기 때문에 중복 방문도 가능하다 생각했고, 경우의 수가 너무 많이 나올 것 같았다. 맵의 벽도 계속 이동 시켜서 넘겨줘야 하는데 너무 비효율적이라는 생각이 들었다. 게다가 DFS의 재귀 + 중복 방문 허용이 합쳐지면 처리를 해주지 않는 이상 무한 루..

2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 문제 읽기 처음에 문제를 읽었을 때에는 dfs를 써야겠다고 생각했다. 그렇게 풀었는데 백트래킹을 제대로 하지 않아서 인지.. 3%에서 계속 시간 초과가 났다 !! 너무 답답해서 그냥 풀이 방식을 바꿔보기로 했다. 글 읽기 - 어디가 틀렸을까요 ㅠ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 위 글을 통해 힌트를 얻었다. 0-1 BFS를 이용하면 될 것 같았다. 잊고 있었던 알고리즘이다. 문제 풀기 0-1 BFS는 BFS처럼 방문..