승1's B(log n)

1) DFS(Depth-First Search) 깊이우선탐색 깊이우선탐색은 캐쥬얼하게 말하자면 깊이 들어갈 수 있을 만틈 들어갔다가 더 이상 들어갈 수 없을 때 뒤로 빠져나와 다른 길로 깊이 들어갔다 나왔다 하는 것을 반복하는 방법이라고 할 수 있다. 말로만 들어서는 어려우니 그림을 보면서 이해해보자. 우선 노드의 인덱스가 0부터 7까지 존재하는 그래프를 생각해보자. 각각의 노드들은 서로 다른 노드들과 연결되어 있는데, 이해의 편의를 위해서 가운데처럼 Adjacency List로 만들어보았다. 인덱스가 0인 노드는 인덱스가 1과 2인 노드들과 연결되어 있고, 인덱스가 1인 노드는 인덱스가 0, 3, 4인 노드들과 연결되어 있다. LIFO(Last In First Out)구조인 스택을 이용하면 DFS를 이..

최대공배수(Least Common Multiple)를 구하기 위해서는 우선 최대공약수(Great Common Divisior를 구하는 법에 대해서 알 필요가 있다. 1) 최대공약수 구하기 최대공약수를 구하는 법은 유클리드 호제법을 이용하면 된다. 유클리드 호제법은 a와 b의 최대공약수를 구할 때 사용이 되는데, a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 공식이다. 이를 코드로 표현해보면 int GCD(int a, int b){ if(a % b == 0) return b; else return GCD(b, a % b); } 이렇게 나타낼 수 있다. 2) 최소공배수 구하기 최대공약수를 구했다면 최소공배수를 구하는 일은 식은 죽 먹기다. 마찬가지로 유클리도 호제법에 의하면 최소공..

이 문제는 어렵기보다는 귀찮고, 재귀될 때마다 달라지는 언더바를 어떻게 구현하는지가 중요했던 문제 같다. 나는 그냥 재귀함수의 파라미터로 n과 k를 받아서 k는 바뀌지 않는 수이자 몇 번의 재귀를 호출할 지 저장하는 수로 사용하고, n은 그 안에서 몇 번째 재귀인지 표시하는 역할로 사용했다. 그렇게 두 가지 인자를 받게 되면 두 가지 인자의 조작을 통해서 언더바와 그 안의 문자열의 개수를 통제할 수 있게 된다. #include using namespace std; void Recursive(int n, int k) { if(n == 0) { for(int i = 0; i < 4 * (k-n); i++) cout

기본적인 방정식을 응용한 문제이다. 그러나 올라가고 떨어지는 것을 번갈아가면서 순차적으로 한다는 점을 주의깊게 봐야 한다. 조건 중에 "정상에 올라간 후에는 미끄러지지 않는다." 라는 부분을 잘 고려해야 이 문제를 맞을 수 있을 것이다. 그리고 추가적으로, 깐깐한 시간 제한 때문에 C++의 cout, cin을 사용할 시에는 시간초과가 날 수도 있으므로 비교적 더 빠른 printf와 scanf를 사용할 것을 권장한다. 답은 맞혀도 시간제한에 걸리면 말짱도루묵이다. #include int main(void) { int A, B, V; scanf("%d %d %d", &A, &B, &V); if(A >= V)//한 번에 올라가는 높이가 올라가야 할 높이보다 높을 때 printf("1\n");//1 출력 els..

흔하디 흔한 소수 문제인 것 같지만 소수들의 합과 최솟값을 출력해야 한다는 점에서 기존 소수를 구하는 문제들과는 차이점이 있다고 할 수 있겠다. 나는 최솟값을 저장할 변수를 아주 큰 수로 초기화하고 소수인 수들을 이미 저장되어 있는 수와 비교함으로써 소수인 수가 더 작은 경우에는 저장하도록 설계했다. #include using namespace std; int main(void) { int N, M; cin >> N; cin >> M; int prime_min = 100000; int prime_sum = 0; for (int i = N; i i) prime_min = i; } } if(prime_sum == 0) cout

이번 문제의 관건은 어떻게 년, 월, 일을 저장할 것이고 그것을 어떻게 비교할 것인가였던 것 같다. 나는 이름을 저장하는 배열 따로, 연도 저장하는 배열 따로, 월 저장하는 배열 따로, 일 저장하는 배열을 따로 만들어서 먼저 연도를 비교하고, 그 다음에는 월을 비교하고, 그 다음에는 일을 비교하는 식으로 수직적인 구조로 구성해보았다. 그리고 맨 마지막에는 for문을 돌려서 가장 적은 나이를 가진 사람과 가장 많은 나이를 가진 사람을 따로따로 저장해서 출력해봤다. #include using namespace std; int main(){ int n; cin >> n; string name[n]; int date[n], month[n], year[n]; for(int i = 0; i < n; i++) { c..

듣지 못한 사람들의 리스트와 보지 못한 사람들의 리스트를 받아서 중복되는 이름이 있으면 그 이름들을 사전순으로 출력하면 되는 문제이다. 리스트에 사전순으로 정렬까지 해야 하기 때문에 이 문제는 파이썬을 이용해서 해결해보았다. import collections num = list(map(int, input().split()))//띄어쓰기로 구분하여 리스트에 정수형으로 각각 듣지, 보지 못한 사람의 수 저장 L = num[0]//듣지 못한 사람의 수는 L에 저장 S = num[1]//보지 못한 사람의 수는 S에 저장 l = list()//입력받을 사람을 저장할 리스트 생성 for i in range(0, L+S): l.append(input())//듣지, 보지 못한 사람들을 구분 없이 한 리스트에 저장 LS..

앞선 글이었던 스택과 크게 다르지 않은 큐 구현이다. 달라진 부분은 스택은 LIFO, 큐는 FIFO 형태이기 때문에 pop이 front냐 back이냐의 차이가 있고, 스택에서는 top()으로 맨 위 원소만 확인할 수 있었던 반면에, 큐는 front()와 back()으로 맨 앞과 맨 뒤 원소를 확인할 수 있다는 차이가 있다. #include #include using namespace std; int main(void) { int N; scanf("%d", &N); queue q; for(int i = 0; i > cmd; if(cmd == "push") { int m; scanf("%d", &m); q.emplace(m); } else if(cmd == ..

STL의 스택을 그냥 사용해서는 안되고, 조금의 변형이 필요한 듯 했다. 그러나 우리에겐 무적의 STL이 있다는 것을 기억해야 한다. #include #include using namespace std; int main(void) { int N; scanf("%d", &N);//몇 번 만큼 명령을 받을 지 입력 받음 stack st;//스택 생성자 for(int i = 0; i > cmd;//어떤 명령인지 string 형으로 입력 받기 if(cmd == "push")//push를 입력 받았을 때는 무엇을 push할 지 추가로 받게 설정 { int m; scanf("%d", &m); st.push(m);//입력받은 숫자를..

이번 문제는 방정식을 푸는 문제라고 할 수 있겠다. 알아둬야 할 점은 최소 개수를 출력해야 하므로 최대한 가능한 만큼 5킬로그램짜리 봉지로 채우는 것이 필요하다는 것이다. 바로 풀이로 이동 #include using namespace std; int main(void){ int I;//이동시켜야 하는 설탕 그램 int x, y; int xmax = -1;//3kg 봉지의 개수 int ymax = -1;//5kg 봉지의 개수 cin >> I; for(y = I; y >= 0; y--)//우선 5kg짜리 봉지의 개수부터 구해야 최소 개수를 구할 수 있음 { if(5 * y