본문 바로가기

공부72

[백준] 11659번 문제출처: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 주어빈 배열의 i번째에서 j번째까지의 합을 구하는 문제이다. 더이상 따로 설명할 것없이 겉으로 보기에는 간단해보였는데 다 쓰고나니 시간초과에 걸렸다. 시간복잡도를 고려해야했다. 배열의 누적합을 구하는 경우, 배열을 모두 훑게되면 시간 복잡도가 O(N^2)으로 늘어난다. 따라서 prefix sum을 위한 배열을 하나 더 만들어주고, 거기에 누적 합을 따로 저장해둔다.. 2022. 6. 15.
[백준] 2331번 문제출처: https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 숫자 A,P가 주어지고, 처음은 A의 자릿수마다 P제곱 해준 값을 모두 더한 값으로 다음 수열값을 시작한다. 이후 그 뒤에 자릿수마다 P제곱의 합으로 다음 수열값을 만든다. 이걸 계속 하다보면 언젠간 같은 부분이 반복되는 지점이 생긴다. 그 반복되는 지점을 싹다 지우고, 남는 원소들의 개수를 구하는게 이 문제의 요지이다. 원소가 어떤게 남아있는지, 혹은 남은 원소의 모든 합을 구해도 좋을 것같은데 그렇게 하면 처리하는 시간이 더 오래걸려서 그냥 문제를 제한시간 2초에 개수를 구하라. 정도로 끝난것.. 2022. 6. 15.
[백준] 1316번 문제출처: https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 실버 5짜리지만 시간이 좀 지나면 브론즈 1로 내려갈 것같기도...?? 한 단어 내에서 같은 알파벳은 연속으로, 그 외의 서로 다른 알파벳은 아무렇게든 붙어있다면 "그룹단어"라 한다. 이 때 그룹단어의 개수를 출력하는 문제다. 맨 처음에는 그룹단어의 개념이 이해가 잘 안됐는데, 예시를 보면서 아하 했다. happy의 경우 그룹단어가 될 수 있는 이유는 같.. 2022. 6. 15.
[백준] 2577번 문제출처: https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 주어진 세 개의 수를 곱하여 나온 숫자에서 0~9까지의 개수를 각각 순서대로 출력하는 문제이다. 숫자의 길이랑 10의 몇 제곱이고를 따지는 것은 불편할 것같아 그 값을 문자열로 바꾸고, 문자열 첫번째 자리부터 '0'이면 0의 개수 count 값에 +1, ..., '9'면 9의 개수 count 값에 +1 하는 식으로 반복했다. 쉬운 단계의 문자열 문제는 이제 어느정도 할 수있을 것같지만, 혹시라도 내가 놓친 것들이나 아직 잘 다루지 못하는 라.. 2022. 6. 15.
[백준] 2740번 문제출처: https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬 기말 공부를 열심히 하자는 의미에서 이 문제를 풀었다. 14일이 행렬 기말고사인데 빨리 공부해야한다. 발등에 불 떨어지다 못해 직접 점화 중이다. 행렬의 곱셈에서, 3x2짜리 A와 2x3짜리 B 행렬이 있을 때 곱셈의 결과는 3x3의 형태로 나타난다. 1,1의 자리에는 A(1,1)*B(1,1) + A(1,2)*B(2,1) + A(1,3)*B(3,1) 1,2의 자리.. 2022. 6. 15.
[프로그래머스] 12906번 문제출처: https://programmers.co.kr/learn/courses/30/lessons/12906 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr 배열을 이용하면 금방 푸는 문제다. 처음에 set를 이용할까 생각해봤는데, 그렇게 하면 순서가 보존되지 않고, 중복되는 모든 수가 사라지기 때문에 두 가지의 문제점이나 발생한다. pop을 이용하는 방법도 생각해봤으나 그렇게하면 i번째 배열에 대한 혼선이 생겼다. 그래서 answer라는 배열을 하나 더 만들어 조건에 맞는 경우.. 2022. 6. 15.