개발자 성장일기

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 해설 2중 for문을 이용할 경우 시간초과가 발생 (n값이 큼) stack을 사용하여 시간문제 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; int n, mp[1000004], ret[1000004], mn; stack s; int main() {..

문제 https://www.acmicpc.net/problem/1325 > n >> m; for (int i = 0; i > a >> b; v[b].push_back(a); } for (int i = 1; i mn) { mn = tmp; ret.clear(); ret.push_back(i); } else if (tmp == mn) { mn = tmp; ret.push_back(i); } } for (int i : ret) cout

문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 해설 트리를 이해하고 있는지 묻는 간단한 문제 1. 루트노드가 0이 아닐때 2. 루트노드가 삭제될때 3. 루트노드만 남을때 이 경우만 잘 고려하면 되는 문제 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 ..

문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 해설 탐색 -> 1을 만날시 해당 값을 변경후 탐색을 멈추도록 구현 bfs / dfs 둘다 가능 => dfs선택 (bfs선택시 메모리 초과 조심) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 해설 bfs / dfs 둘다 가능 모든 경우의 수를 구해야하는 문제....(n,m크기 && 시간초 보고 빠르게 판단해야함) 무식하게 접근하는게 답이였다. => 그 과정에서 여러 변수들을 잘 통제해야함 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4..

문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 해설 9012번과 거의 비슷한 문제 "짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다." 이 조건만 조심하면 되는 문제 스택 top참조시 사이즈 체크 먼저 할것 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 해설 전형적인 스택 문제 함수로 만들어서 구현하면 check함수를 없애며 조금 더 단조롭게 코드를 짤 수 있음 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include using namespace std; int t;..

문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 해설 규칙성이나 방법을 찾으려다가 오래 걸린 문제... 시간이 2초 주어졌고 n의 크기가 10000이라 연산해야하는 값이 1000만개가 넘지 않음 => 각 수당 약 20번의 연산가능 모든 경우의 수를 그냥 비교해 보는 문제 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int n; int main(..

문제 https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1 1이기는중 / 2이 이기는중 -> 무승부 / 무승부 -> 2이기는중 에 대한 구분을 잘해야함 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include using namespace std; int n, mm, ss, team, t1, t2, totalsec, winer, s1, s2; int main() { scanf("%d", &n); for (int i = 0; i..

문제 https://www.acmicpc.net/problem/3474 3474번: 교수가 된 현우 첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 5를 포함 -> 2도 포함 -> 10완성 5포함 확인 후 -> 25포함확인 -> 125 포함확인의 순서를 진행 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; int t, n, ret; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; for (int i = 0; i ..