승1's B(log n)

C++이나 C를 공부하다보면 const keyword가 많이 등장하곤 한다. 사실 그동안 과제를 할 때나 수업을 들을 때나 const라는 키워드만 보면 두려웠다. const의 개념을 확실히 이해하지 못하고 그저 상수화 해주는 키워드라고만 알고 있었기 때문이다. 따라서 이번 기회에 const에 대해 확실하게 알아보고자 한다. 1) const 키워드의 개념 : const 키워드는 값을 상수로 선언할 수 있도록 도와주는 키워드이다. const 키워드를 통해 한 번 설정된 값은 read-only memory에 저장된다. 따라서 상수화된 이후에는 값을 변경할 수 없다. 2) const 키워드는 포인터 선언에도 사용할 수 있다. #include using namespace std; int main(void) { c..

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

이 문제는 어렵기보다는 귀찮고, 재귀될 때마다 달라지는 언더바를 어떻게 구현하는지가 중요했던 문제 같다. 나는 그냥 재귀함수의 파라미터로 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..

앞선 글이었던 스택과 크게 다르지 않은 큐 구현이다. 달라진 부분은 스택은 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

이 요상한 큐 문제는 각 요소마다 중요도가 있어서, 자기보다 더 중요한 요소가 존재하면 무조건 맨 뒤로 이동시키게 된다. 그래서 지정된 요소가 몇 번째로 출력이 되는가를 알아내는 프로그램을 작성하는 것이 이 문제의 목적이 되시겠다. 문제를 풀기 전에 고려했던 것은 어떤 컨테이너를 쓸 지였는데, 일반 queue를 쓰자니 중요도를 상호간 비교할 수가 없을 것 같아서 결국엔 앞뒤 push, pop이 되고 iterator를 사용할 수 있는 deque를 사용하기로 했다. #include #include using namespace std; int main(void) { int n; scanf("%d", &n);//총 몇 번을 수행할 것인지 for(int i = 0; i < n; i++) { deque dq;//덱..