1. 시간 초과 -> 시간복잡도를 고려하자 (자료구조, 알고리즘구조, 누적합) 런타임 에러 -> 인덱스 초과 참조, 음수 인덱스 참조 분모에 0 자료구조 empty 상태에서 pop(), top() 틀렸습니다 -> 예외처리 (문제해석할 때 예외 파악하기) 2. 변수를 전역으로 초기화할 때 지역변수로 반복 초기화해야하는지 확인 3. 구현 단계를 나눠서 코딩해야 단계별 디버깅 가능 4. 구현할 때 시간이 적게 걸리는 방법을 고려하는 습관 5. 입력 혹은 출력 형식이 특이할 때 예외처리를 확실히 해야한다. ex) [1,2,3] 과 같은 형태로 정수를 입력받을 때 모든 경우 char를 처음에 한 번, 정수 뒤에 한 번씩 받으면 되지만 [] 입력값이 없는 경우만 처음에 한 번, 정수가 없어도 마지막에 한 번 받도록..
PS
2493. 스택의 시간복잡도 (Monotonic Stack) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [풀이] 벡터로도 풀 수 있고 스택으로도 풀 수 있는 문제이다. 하지만 첫 번째 코드인 벡터을 사용한 코드는 시간초과가 발생하고 두 번째 코드인 스택을 사용한 코드는 solved 를 받는다. 두 코드 모두 for문 안에 while 문이 들어간 시간 복잡도 O(N) 코드처럼 보이는데 왜 실행 시간이 다를까 (물론 vector가 아닌 배열..
2559. 누적합 (prefix sum)https://www.acmicpc.net/problem/2559 2559번: 수열첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기www.acmicpc.net[풀이] 누적합을 이용한 풀이를 생각해내지 못하면 시간초과를 받게되는 문제이다. 나 또한 그랬다. 첫 번째 코드는 누적합 없이 푼 코드이다. → 시간초과 참고로 accumulate()는 O(N)이며 해당 코드의 시간복잡도는 O(N^2)이다.#include using namespace std; vector input; int N, K, in, maxim..
9996. 예외처리 https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net [풀이] substr()과 find()를 사용해서 구현할 수도 있고 나처럼 reverse()를 사용해 구현할 수도 있다. 패턴에서 앞에서부터 *가 나올 때까지를 파일이름의 앞에서부터 비교하고, 패턴에서 뒤에서부터 *가 나올 때까지를 파일이름의 뒤에서부터 비교하며 패턴과 파일이름이 다르면 flag++ 한다. 이 때 예외처리를 생각하지 못해서 많이..
3273. 런타임에러(OutOfBounds)https://www.acmicpc.net/problem/3273 3273번: 두 수의 합n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는www.acmicpc.net [풀이] 위 문제를 풀면서 런타임에러를 7번이나 받아서 왜 런타임에러가 발생했고 어떤 부분에서 주의하면 되는지 설명도 하면 좋을 것 같다.런타임 에러는 1) 0으로 나눴을 때 2) 배열에 존재하지 않는 인덱스를 참조했을 때 2번의 경우에 배열의 크기를 초과한 인덱스를 참조하는 경우, 배열의 음의 인덱스를..
10988.https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.www.acmicpc.net [풀이]#include using namespace std; string input; int flag; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> input; for (int i=0; i
10804. https://www.acmicpc.net/problem/10804 10804번: 카드 역배치 1부터 20까지 오름차순으로 놓인 카드들에 대해, 입력으로 주어진 10개의 구간 순서대로 뒤집는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다. www.acmicpc.net [풀이] 배열 혹은 문자열의 내부 요소를 뒤집는 STL지원 함수 reverse()를 사용하면 된다. 배열에서는 reverse(a, a+5) 와 같이 사용하면 되고 문자열에서는 reverse(a.begin(), a.begin + 5) 와 같이 사용하면 된다. #include using namespace std; int card[20]; int a,b; int main(){ ios::sync_with_stdio(0); c..
2309. 조합 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] 순열, 조합 문제이며 세 가지 풀이가 있다. 첫 번째로, 직관적으로 9명 중 7명을 선택하는 조합 문제로 해결할 수 있다. 조합 문제는 크게 이중 for문, 재귀함수 두 가지 방법으로 풀 수 있는데 9C7은 9C2이므로 이중 for문으로 조합을 구현하는 것이 가장 쉽다. ( 3중까지는 중첩 for문으로 작성하는 것이 좋다. ) #include using namespace std; ..
1053. [풀이] c++에는 참 거짓을 나타낼 수 있는 자료형 bool 이 있다. 다른 자료형의 값을 bool()을 통해 ture or false 로 나타낼 수 있다. #include using namespace std; int main(void) { bool a; cin >> a; cout > a; cout > a >> b; int result = a & b; cout > a >> b; a > b ? cout > b; max(a,b); } 1064. [풀이] 세 가지 정수를 비교하는 삼항연산자는 더 복잡해 보이지만 원리는 같다. #include using namespace std; int main(){ int a, b, c; cin >> a >> b >> c; (a < b && a < c) ? cout
1031. [풀이] #include using namespace std; int main(){ int a; cin >> a; printf("%o", a); } 1032. [풀이] #include using namespace std; int main(){ int a; cin >> a; printf("%x", a); } 1034. [풀이] #include using namespace std; int main(){ int a; scanf("%o", &a); cout > a; cout > a; cout
