본문 바로가기

분류 전체보기74

[백준] 1010번 문제출처: https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 순열과 조합을 이용하는 문제같았다. 각 테스트 케이스에 대해 다리를 지을 수 있는 경우의 수를 출력하는 것이다. 예제를 확인해보니 순서는 고려하지 않는 것같았다. 그래서 선택 점이 같은 경우의 수는 빼줘야 했다. (중복되지 않도록.) 그래서 반복문을 만들어 순열과 "조합"의 형태를 만들어냈다. 2022. 6. 15.
[프로그래머스] 42587번 문제출처: https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 순서대로 입력받은 인쇄물을 중요도에 따라 재정렬하여, 내가 입력한 출력물은 몇 번째로 나오는지 구하는 것이다. key, value가 있어야하기 때문에 dictionary를 생각해봤는데, dict는 정의하고 시작하는 방법밖에 떠오르지 않아서 패스. enumerate 기능을 사용했다. for 문에서 자주 등장시켰던 기능이다. deque 안에 enumerate.. 2022. 6. 15.
[백준] 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.

티스토리툴바