시간 제한 메모리 제한 1초 1024MB 문제 여중생 파댕이는 할 것이 너무 많고 공부가 어려워 정신이 없다. 오늘도 여중생 파댕이는 선생님으로부터 덧셈 문제 풀기라는 끔찍한 과제를 받았다. 파댕이는 어찌어찌 과제를 다 하는 데는 성공했지만, 과제를 채점하는 일이 매우 귀찮았다. 그래서 파댕이는 과제를 읽고 자동으로 채점해 주는 프로그램을 개발하려 한다. 파댕이를 도와주자! 이하의 문단들은 문제의 요구 조건을 자세히 기술한 것이다. 직관적인 설명을 원한다면 입력 예시와 출력 예시를 참고하라. 파댕이의 과제가 적힌 종이는 크기 3N × 8M의 행렬로 나타낼 수 있다. 종이 위에는 여러 개의 문제가 적혀 있는데, 하나의 문제가 차지하는 공간은 세로 3, 가로 8이다. 이 문제들이 세로로 N개, 가로로 M개씩..

시간 제한 메모리 제한 1초 1024MB 문제 유치원생 파댕이는 아직 어리기 때문에 단것을 매우 좋아한다. 또한, 파댕이는 사탕을 주지 않으면 시도 때도 없이 울곤 한다. 파댕이를 사랑하는 여러분은 일정 시간 동안 파댕이를 돌봐주기로 했다. 여러분은 파댕이를 돌보는 동안 파댕이가 우는 것을 보고 싶지 않기에, 파댕이가 울지 않도록 사탕을 챙겨왔다. 하지만 파댕이를 빨리 보고 싶은 마음에 급하게 사탕을 챙기느라, 돌보는 동안 파댕이가 울지 않게 만들 수 있는 충분한 사탕의 개수인지 확인하지 못했다. 여러분이 가지고 있는 사탕으로 파댕이를 돌보는 동안 파댕이를 울지 않게 만들 수 있는지 알아보자! 여러분은 T분 동안 파댕이를 돌봐야 하며, N개의 사탕을 가지고 있다. 파댕이는 사탕의 맛에 따라 울음을 그치는..

시간 제한 메모리 제한 1초 256MB 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람들이 서 있는 순서대로 입력이 주어진다. 출력 서로 볼 수 있는 ..

트리(Tree) 자료구조는 데이터간 위계가 있어 다양한 처리가 가능하다. 세그먼트 트리는 약간의 메모리를 할애해 구간의 값을 따로 관리하여 빠르게 구간 해를 얻도록 하는 트리이다. 세그먼트 트리는 데이터 전체 구간을 반복적으로 이분해 정복하여 구간에서 원하는 값을 저장해 빠르게 얻도록 한다. 원하는 값이라고 한다면 "구간의 합, 곱", "구간 내 최대, 최소 값" 등이 가능하고 분할 정복으로 구간의 해를 얻을 수 있는 문제라면 세그먼트 트리를 적용할 수 있다. 세그먼트 트리는 데이터 접근에서 정확도가 요구되기 때문에 처음에는 구현하기가 매우 까다롭다.(진짜 개고생했다.) 우선 이 글에서는 새로운 데이터를 추가하지 않는 조건에서 세그먼트 트리를 만들고 원하는 구간 해를 출력하는 쿼리를 구현해본다. 1. 트..

1. 행렬의 곱셈행렬의 곱셈은 단순히 곱셈보다 압도적으로 많은 연산을 필요로 한다. 행렬의 규모가 커질수록 그 정도는 더 심화된다. 행렬의 곱셈은 아래와 같은 규칙을 따른다.2*2 크기의 정사각행렬 두 개를 곱할 때 필요한 연산은 덧셈 4회, 곱셈 8회이다. 3*3 정사각행렬은 덧셈 18회, 곱셈 27회가 필요하다. 연산 횟수로 보았을 때 n*n크기의 정사각행렬의 곱셈은 O(n3)의 시간복잡도를 갖는다. 지수시간이 아닌게 어디겠냐만 이걸 더 줄이는 알고리즘이 여럿 존재한다. 행렬의 곱셈은 공학분야에서 폭넓게 활용되기 때문에 효율적인 연산 방법을 찾는 연구가 꾸준히 진행되고 있다. 최근에는 구글 딥마인드의 알파제로가 새로운 행렬 곱셈 알고리즘을 발견하기도 했다. 아무튼 다양한 방법 중 깡 삼차시간 연산 방..

분할 정복으로 정렬을 완성해가는 알고리즘이다. 알고리즘은 분할, 병합의 두 단계를 재귀 호출하는 것으로 완성되어 꽤 단순하게 구현할 수 있다. 그 유명한 폰 노이만 박사가 만든 알고리즘이다. 1. 병합 정렬(Merge sort)의 개념 원리는 앞서 말한 분할 정복(Divide and Conquer)이다. 문제 전체를 부분으로 쪼개서 하위 문제의 해를 찾아 상위 문제의 해를 얻는 방식으로 정렬에 적용하면 전체 길이의 배열을 절반, 다시 절반, 반복하여 나눌 수 없는 상태의 크기로 만들고 정렬이 끝난 부분들을 합쳐 정렬을 점차적으로 완성해나간다. 이 일을 진행할 때 코드에서 구현해야 하는 것은 두 가지다. 먼저 "분할"하는 것이고 분할된 것을 바르게 "병합"하는 것이다. 언제 분할하며 언제 병합하는지도 중요..

시간 제한 메모리 제한 1초 256MB 문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이 1. 1트 누적 합 알고리즘만 써서 제출 해봤더니 시간초과가 떴다. import sys input = sys.stdin.readli..

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..