오답노트

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net -문제 파악 배열돌리기1 의 시간복잡도 버전 - 나의 접근 배열을 돌렸을 때 첫번째 배열로 돌아오는 수를 찾아서 문제에서 주어지는 돌리는 횟수를 나눈 나머지 만큼만 돌릴려고 했지만, 돌아오는 수가 너무 큰건지 계속 런타임 오류가 발생했다. - 정답 그래서 가장 바깥 배열부터 차례대로 위의 접근 방식을 적..

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net - 문제파악 NxM 배열이 주어지고 가장 밖에 원소들부터 안쪽으로 반시계 방향으로 요소들을 한 칸씩 옮긴 결과를 출력하라 - 정답 디버그 모드로 돌려서 노가다 했다. #include "bits/stdc++.h" using namespace std; int n, m, t; int arr[305][305];..

https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net - 문제 파악 문제에서 요구하는 배열 돌리는 기능을 구현하여 입력으로 주어지는 NxM 배열을 돌린 결과를 출력하라 - 정답 #include "bits/stdc++.h" using namespace std; int arr[104][104]; int n, m, t; void func1() // 상하 반전 { int k = n..

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까지 배열들 중에서 자신보다 작은 수열들이 존재하면, 자신 보다 작은 수..