https://www.acmicpc.net/problem/10986누적합(prefix sum)먼저 누적합이란 나열된 수의 누적된 합을 말한다. 만약 [1, 2, 3, 4, 5] 라는 배열이 있고, 이 배열을 누적합으로 나타낸다면 [1, 3, 6, 10, 15] 가 된다. 보통 반복문을 통해 `0번 index부터 4번 index까지의 누적합`을 구한다면 5번의 수행동작이 필요하다. 즉 O(N)의 시간 복잡도를 갖는 것이다. 하지만 누적합을 사용하여 `0번 index부터 4번 index까지의 누적합`을 구한다면 누적합 배열의 4번 index 값을 꺼내오기만 하면 되기 때문에 O(1)의 시간 복잡도를 갖는다. 그렇다면 `2번 index부터 4번 index까지의 누적합`을 구하기 위해서는 어떻게 해야할까? (1..

https://www.acmicpc.net/problem/11444인사이트이번 문제는 우리들이 사랑하는 피보나치 수열이다. 피보나치 수열이 골드2까지 난이도가 책정된 이유에는 입력값의 크기 제한에 있다. 일반적으로 1초에 대략 1억번 정도의 연산이 처리된다는 것을 감안하면, 입력값의 최대값이 1000억이기 때문에 dp를 사용해서 O(N)의 시간 복잡도로 처리해도 시간 초과가 날 것임을 예상할 수 있다. 그렇기 때문에 피보나치 수열의 일반항으로는 어떤 짓을 해도 시간초과를 해결할 수 없을 것이다. 해서, 이 피보나치 수열의 일반항에서 시간 처리를 극적으로 줄일 점화식을 고안해내야 한다. 여기서 한가지 더 생각해보면 1000억이란 숫자를 1억 내로 안정적으로 줄이려면 제곱근으로 접근하는 것 외에는 거의 방법..

https://www.acmicpc.net/problem/17114문제 해설이번 하이퍼 토마토 문제는 지난 토마토 문제에서 배열의 깊이가 2차원에서 11차원으로 변형된 심화 문제입니다.  [백준 / BOJ] 7576번 토마토 ( Node js / Javascript )https://www.acmicpc.net/problem/7576  문제 풀이토마토는 BFS의 대표 문제들 중 하나입니다. 만약 BFS 혹은 그래프 탐색 자체에 대한 지식이 부족하다면 아래 링크를 참고하시길 바랍니다. 너비 우선 탐dnd0707.tistory.com 언뜻 보기에는 11차원이라는 말도 안되는 조건 때문에 괴랄해 보이겠지만 사실은 보이는 것 만큼의 난이도를 가진 문제는 아닙니다. 만약 만약 x축이 이동할 때 동시에 y축도 이동이..

https://www.acmicpc.net/problem/7576  문제 풀이토마토는 BFS의 대표 문제들 중 하나입니다. 만약 BFS 혹은 그래프 탐색 자체에 대한 지식이 부족하다면 아래 링크를 참고하시길 바랍니다. 너비 우선 탐색(BFS)와 깊이 우선 탐색(DFS)BFS(Breadth-First Search)와 DFS(Depth-First Search)는 그래프 탐색 알고리즘의 두 가지 주요 유형으로, 그래프의 데이터를 탐색하는 데 사용됩니다. 이 두 알고리즘을 이해하기 위해서는 그래프가 무엇인dnd0707.tistory.com 본인이 떠올린 문제 해결 방안은 다음과 같습니다.1. 배열을 순회하며 1의 위치들 즉, 시작점들을 큐에 넣어준다.2. 시작점들이 담겨있는 큐로 BFS를 실행한다.    방문 ..

1107번: 리모컨첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이www.acmicpc.net 문제 풀이 고장나지 않은 버튼들만을 이용해서 목표 채널까지 버튼을 가장 적게 눌러 도착하면 된다. 그런데 입력 조건을 보면 목표 채널의 최대값이 500,000인 것을 확인할 수 있다. 즉, 채널을 1부터 하나씩 모두 검사해도 처리시간이 매우 적게 나온다는 것이다.그렇다면 이 문제는 브루트포스를 사용해 손쉽게 해결할 수 있을 것 같다. 그렇다면 우리는 최악의 경우인 목표 채널이 500,000 번이고, 9를 제외한 모든 숫자가 고장났다고 했을 때를 감..

1인 경우, 배열을 " data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1074" data-og-url="https://www.acmicpc.net/problem/1074" data-og-image="https://scrap.kakaocdn.net/dn/cWSnN9/hyVDAKuYll/mblD9ou5AdVp4Ztmo2lK3K/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/cGdciu/hyVAIQTLHK/K7DoNQ8vtdQXsPr6fybkw0/img.png?width=1066&height=1070&face=0_..