Algorithm (109) 썸네일형 리스트형 [백준][C++] 11660: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net - 문제 2차원 배열상의 표가 주어지면 (x1,y1)부터 (x2,y2)까지의 합을 구하는 문제다. - 해설 구간 합 구하기 4까지는 일차원 배열 문제라 쉬웠는데, 이것도 이차원 배열이라는 거 빼고는 다를 게 없다. 가장 먼저 값을 어떻게 넣어줄건지를 생각해야 한다. (가로로 먼저 더하고 세로로 더하는 방법을 사용했다.) 1 2 3 4 2 3 4 5 3 4.. [백준][C++] 16139: 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net - 문제 문자열이 주어지면 l번째 문자부터 r번째 문자 사이에 나타나는 문자 a의 횟수를 출력하는 문제다. - 해설 서브태스크 1에 문자열의 길이는 2,000자 이하라고 되어있지만, 이렇게 문제를 풀면 50점밖에 못받는다.!!!! 100점을 맞으려면 입력에 주어지는 1 S >> q; counts[S[0] - 'a'][0] = 1; for (int .. [백준][C++] 2559: 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net - 문제 수열이 주어지면 K 길이의 합이 최대인 경우를 구하는 문제다. - 해설 1 2 3 4 5 6 7 8 9라는 수열이 있으면 4 부터 8까지의 합은 8까지의 합 - 3까지의 합이 되므로 반복문을 총 길이 - K번 만큼 돌려서 최대값을 구하면 된다. - 풀이 #include #include using namespace std; int main() { ios_base::sync_wi.. [백준][C++] 11659: 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net - 문제 i번째 부터 j번째 수까지 합을 구하는 문제다. - 해설 i부터 j까지 합을 계속 반복문으로 돌리면 시간초과가 나는 문제다. 0 1 2 3 4 5 6 7 8 9 라는 수가 있으면 4부터 7까지의 합은 7까지의 합 - 3까지의 합이 된다는 것을 이용해서 풀면 된다. - 풀이 #include #include using namespace std; int main() { .. [백준][C++] 2580: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net - 문제 스도쿠가 주어지면 빈칸에 들어갈 숫자를 맞추는 문제다. - 해설 혼자서 풀다가 잘 안되어서 내가 자주 참고하는 cryptosalamander라는 블로그의 내용을 참고해봤다. 역시 언제나 그렇듯 코드가 되게 깔끔하게 잘 짜여져 있었다. 나는 스도쿠 판을 9*9 모든 경우를 돌면서 문제를 해결하려고 해서 시간초과가 났지만, 이 분은 비어있는 0인 경우의 좌표를 기억해놔서 해당 경우만 정답을 .. [백준][C++] 1912: 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net - 문제 연속적인 수 중에서 가장 큰 값일 때를 구하는 문제다. - 해설 이전의 값이 음수더라도 지금까지 더한 값이 0보다 크면 계속 더해가는게 좋고, 0보다 작으면 새로 시작하는게 낫다는 생각으로 문제를 풀면 된다. - 풀이 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(N.. [백준][C++] 9461: 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net - 문제 피보나치 수열과 비슷한 형태의 문제를 해결하는 문제다. 다만, n-1 + n-2가 아니라 n-2 + n-3이다. - 해설 메모이제이션과 피보나치 수열의 변형을 이용해서 풀면된다. 신경써야 할 점으로는 - 시간 초과 - 자료형 이 있다. 메모이제이션 없이 dfs 느낌으로 풀면 시간초과가 날 수 밖에 없고, 피보나치 수열과 같은 형태의 문제는 n이 100까지만 가더라도 int 자료형으로는 감당할 .. [백준][C++] 10773: 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net - 문제 스택을 이용해서 숫자를 저장하거나 빼고 스택에 남은 정수를 합치는 문제다. - 해설 stack을 이용해서 풀면 된다. - 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int K, temp.. 이전 1 2 3 4 5 6 7 ··· 14 다음