백준84 [5430] AC https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net AC 욕 나오는 문제이다 ㅎㅎ~ 분명 쉬워보였는데 왜 때문에 자꾸 오류가 뜨는건가.. char 배열에서 범위 제한에서 자꾸 틀렸습니다가 나와서 그냥 string으로 바꿨더니 해결되었다. 너무나도 빡침 이 문제를 푸는데 크게 2가지 걸림돌이 있었다. 1. 문자열 parsing 큐 문제에 껴있었으면서 문자열 parsing에서 많이 애먹어서 화남 strtok 함수도 써보았으나 왜때문인지 잘 안돼서 냥 쉼표나 닫히는 대괄호가 들어오면 하나의 정수값을 완성시켰다.. 2023. 1. 31. [1021] 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 덱 문제이다. 덱(deque)은 양방향에서 push, pop이 가능한 큐이다. 궁금한 원소가 주어졌을 때 해당 원소가 빠져나가는데 필요한 2번 연산과 3번 연산의 횟수를 구하는 문제이다. ** 1번 연산은 횟수에 포함되지 않음! ** 연산 횟수의 최솟값은 어떤 기준으로 구분하는게 좋은지 고민하면 된다. N=10, M=3, 순서대로 2, 9, 5의 연산 횟수 최솟값이 궁금할 때의 예시이다. 난 .. 2023. 1. 30. [1966] 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐 문제이다. 내가 알고싶어하는 문서가 queue의 몇 번째에 들어가있는지, 그리고 이것을 따져가며 출력을 해야했기에 살짝 까다로웠다. 일단 queue를 생성해야 한다. 내가 원하는 문서의 queue 순서를 표시해줘야하기 때문에 queue를 구조체로 생성하였다. struct mymy { int idx; bool isCheck = false; }; queue myqueue; isCheck이 true라면.. 2023. 1. 26. [11866] 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 큐 문제이다. K번째에 나오는 수를 계속해서 버리면서 수열을 출력하는 것이다. N=7, K=3일 때 이 과정을 코드로 구현하면 아래와 같다. #include #include using namespace std; int N, K; queue myqueue; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; for (int i = 1; i 2023. 1. 26. [1874] 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택 문제이다. 조금 생각이 필요했다. 문제 이해 자체가 조금 힘들었는데, 1~n까지 수에 대해 오름차순으로 입력 받는다고 가정할 때 push, pop의 순서를 출력하는 문제이다. 백준에 나온 예제를 예시로 들어보면 이렇게 된다. 직접 써보니 일단 push를 먼저한 후, 조건에 따라 pop을 해야겠다고 생각했다. 대.. 2023. 1. 19. [9012] 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택 문제이다. 괄호가 완전히 닫혀있는 꼴이면 YES, 아니면 NO를 출력하는 문제이다. 굉장히 쉽게 풀었는데 배열 길이를 50으로 해서 틀렸었다. 무조건 배열 길이는 지정한 것보다 1 크게 하자는 교훈을 얻었다. '('이 입력되면 push, ')'이 입력되면 pop을 해주는데 이 때 stack이 비어있는 상태에서 pop을 시도하면 VPS가 아니므로 NO를 출력해주었.. 2023. 1. 17. [10986] 나머지 합 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합 문제이다. 처음에 이중for문을 썼더니 시간 초과가 나서 2시간동안 풀었다. 질문 게시판에 설명되어있던 알고리즘을 참고하여 풀었다. 누적합을 M으로 나눈 나머지가 같은 것들끼리 빼면 나머지가 0이 되어 딱 나누어 떨어지게 된다. 그 점을 이용하기 위해 L배열을 만들었다. 그리고 나머지가 같은 것들끼리의 구간합이 총 몇 개인지 알기 위해 R배열.. 2023. 1. 16. [16139] 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 2차원 배열 누적합 문제이다. 알고리즘은 맞았는데 마지막에서 삽질해서 시간이 조금 걸렸다. S[i][j] : 0~i까지 알파벳 j의 누적합 으로 설정했다. 알파벳 j는 입력을 받은 후 아스키 코드에 맞춰 97을 빼주고 계산하였다. 누적합을 구하는 건 금방했는데, 구간별 누적합을 구하는 데에 오랜 시간이 걸렸다. l이 들어올 때 0이면 처음부터 탐색.. 2023. 1. 12. [25682] 체스판 다시 칠하기 2 https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 누적합 문제이다. 시간 초과를 도저히 해결할 수 없어서 인터넷의 힘을 빌렸다. 일단 2차원 배열 누적합 문제이기에 전에 풀었던 11660번 구간 합 구하기 5를 참고하였다. https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있.. 2023. 1. 11. [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 누적합 + 동적 프로그래밍 문제이다. 처음에 푼 것과 다시 푼 것 모두 설명해보려 한다. 1. 행 누적합 행과 열을 합쳐서 누적합을 구하기 어렵다고 판단하여 행의 누적합을 2차원 배열에 담았다. A[i][j]를 i행에서의 1~j열까지의 합으로 정의하였다. 예를 들어 A[1][3] = 1 + 2 + 3 = A[1][2] + 3 = 6 A[4][2] = 4 .. 2023. 1. 9. 이전 1 2 3 4 5 ··· 9 다음
