오답노트

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 문제파악 수빈이와 동생의 위치가 정수로 주어진다. 수빈이 위치에서 동생 위치로 가기위한 최소 시간을 출력하라 - 정답 주의해야하는 점 문제의 조건중에 순간이동은 0초가 걸린다. 그래서 순간이동을 했을 때 최소 시간이 0초가 될 수 있다. 예를 들어 동생이 2의 배수에 위치한다면 수빈이는 0초만에 이동 가능하다. (부럽다.) #include "bits/stdc+..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 문제 파악 수빈이의 위치와 동생의 위치가 정수로 주어지고 1차원 배열에서 수빈이 위치에서 동생 위치로 가는 최소 시간과 경로를 출력하라 -정답 주의가 필요했던 점 1. 수빈이 위치에서 동생 위치로 가는 최소 경로 출력 메모리 초과 발생하여 경로를 저장하는 배열을 조건문안에 넣어 최대한 메모리를 덜 차지하도록 했다. 2. 수빈이와 동생의 위치 차이가 동일할 때 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net - 문제파악 NxN 배열이 주어지고 배열 내에 값은 0과 1이 주어진다. 1이 상하좌우로 붙어있다면 인접해있다고 한다. 1이 인접한 그룹의 개수(단지의 개수)와 그룹내의 1의 개수(단지 내 건물 개수)를 출력하라 -정답 BFS로 풀이했다. 처음에 큐에 푸쉬하는 것도 체크해야한다. #include "bits/stdc++.h" using namespace std; int arr[26][26]; int ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net - 문제 파악 정점의 개수와 간선의 개수가 주어지고 연결 요소의 개수를 출력하라 연결 요소 : 간선으로 이어진 정점들을 한 개의 연결 요소로 볼 수 있다. 간선으로 이어지지 않고 단독으로 있는 정점도 연결요소로 볼 수 있다. - 정답 #include "bits/stdc++.h" using namespace std; int arr[100..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net - 문제 파악 덱을 구현하는 문제이다. - 정답 덱은 앞으로도 뒤로도 값을 넣을수 있고, 반대로 앞으로도 뒤로도 값을 뺄수 있다. #include "bits/stdc++.h" using namespace std; int arr[10002]; int nsize = 0; void push_front(int k) { for (int i = nsize-1; i >= 0; i--) { ar..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net - 문제파악 큐의 구조를 파악할 수 있는 문제 - 정답 큐는 선입선출이다. 즉 먼저 들어온 요소가 나갈때도 먼저 나간다. 해당 문제에서 pop과 같다. C++ stl에서 queue를 제공하고 있다. #include "bits/stdc++.h" using namespace std; int arr[10002]; int nsize = 0; void push(int k) { arr[nsi..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net - 문제 파악 수열이 주어지고, 수열 중 일부를 선택하여 감소하는 부분 수열을 만들 수 있는 경우 중에서 수열의 길이가 가장 긴 값을 출력하라. - 정답 가장 긴 증가하는 부분 수열 감소 버전이다. 기준이 되는 수열을 하나 지정하고(i), 0부터 i-1까지 배열들 중에서 자신보다 작은 수열들이 존재하면, 자신 보다 작은 수..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net - 문제 파악 N개의 수열이 주어진다. 주어진 수열로 증가하는 부분 수열을 만들수 있는데, 그 수열들 중 합이 제일 큰 값을 출력하라. - 나의 접근 이전에 증가 부분 수열에 관한 문제를 두문제나 풀어 놓고 같은 유형의 문제를 다시 틀렸다. (제대로 복습을 안했겠지) 이중for문 까진 생각했지만, 점화식을 이끌어내는 부분에서 막혔다. 정답..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net - 문제 파악 정수 N이 주어지고 크기가 N인 삼각형이 주어진다 이 중에서 수를 선택할 수 있는데 선택한 수의 다음 줄의 왼쪽 또는 오른쪽만 선택할 수 있다. 이렇게 선택한 수들의 합의 최대값을 출력하라 - 정답 무식하게 요소에 접근 할때마다 이전까지 더했던 값의 합과 현재 요소를 더했을 때 큰 값을 남기도록 했다. 시간제한 2초 정도면 이중for문으로 무식하게 풀어도 되나보다. #include "bits/stdc++.h" using namespace std; int ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net - 문제파악 정수 n과 n개 배열을 주어진다 연속해서 3개를 선택하지 않는 경우중에서 선택한 배열의 합이 가장 큰 경우를 출력하라 - 나의 접근 백트래킹으로 풀었는데 시간초과였다. 메모제이션으로 시도 했으나 점화식을 제대로 세우지 못했다. - 정답 D[i] 는 주어진 배열의 합중에서 가장 큰 값을 넣는다. 포도주를 먹는 경우는 아래 처럼 정리할 수 있다. 지금 안마시는 경우 : D[i - 1] 이전..