study

1929번만 블로그에 올리려다가 1110번 처음 제출했을 때 틀려서 1110번도 그냥 올리기로 결정!! 쉬운 문제들은 사실 코드 올리기도 좀 머쓱머쓱한데 그래도 내가 첫 번째 제출 때 틀렸으니까!!! 올린다!!!! 백준 1110번 www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 : 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 ..

1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다. 1. 2부터 N까지 모든 수를 써놓는다. 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 3. 그 수는 소수이다. 4. 이제 그 수의 배수를 모두 지운다. 1에서 120까지 소수를 찾는다고 할 때를 생각해보자. 밑의 그림이랑 보면 쉬울 거임! 2부터 120까지 모든 수를 써놓고 아직 지워지지 않은 수 중에서 가장 작은 수를 찾자. 2가 제일 작은 수이고 소수이므로 2의 배수를 모두 지운다. (움짤에 빨간색) 그다음 3이 제일 작은 수이고 소수이므로 3의 배수를 모두 지운다. (움짤에 초록색) 그다음 4는 지워졌고 5가 제일 작은 수이고 소수이므로 5의 배수를 모두 지운다. 그리고 7의 배수를 지우고 이다음..

(A+B) mod M = ((A mod M) + (B mod M)) mod M (A*B) mod M = ((A mod M) * (B mod M)) mod M 뺄셈의 경우에는 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다. (A-B) mod M = ((A mod M) - (B mod M) + M) mod M 최대공약수(GCD)는 유클리드 호제법을 이용하는 방법이 제일 좋다. 유클리드 호제법 : a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a, b) == GCD(b, r) 그래서 r==0 일 때의 b값이 최대공약수이다. 재귀 함수를 사용해서 유클리드 호제법을 구현해보자!! inc gcd(int a, int b) { if (b == 0) { return a; } else {..

다 스택에 관한 문제들이다. 백준 17413번 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 : 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

이거 수업시간에 배웠을 때는 교수님이 데크라고 부르시던데 남들은 다 덱이라고 쓰니까 나도 덱이라고 써야지!!ㅋㅋㅋㅋㅋ 덱(deque)은 double-ended queue의 약자로 양방향 큐이다!! 그러니까 큐에서는 앞에서 pop이 일어나고 뒤에서 push가 일어나는 대기줄이라고 말했었는데 덱은 앞에서도 pop과 push가 가능하고 뒤에서도 pop과 push가 가능하다. 덱의 method는 push_front : 덱의 앞에 자료를 넣는 연산 push_back : 덱의 뒤에 자료를 넣는 연산 pop_front : 덱의 앞에서 자료를 빼는 연산 pop_back : 덱의 뒤에서 자료를 빼는 연산 front : 덱의 가장 앞에 있는 자료를 보는 연산 back : 덱의 가장 뒤에 있는 자료를 보는 연산 등이 있다...

큐(Queue)는 뒤에서 자료를 넣고 앞에서 뺄 수 있는 자료구조이다. 대기줄을 생각해보면 된다. 놀이공원에 줄을 섰을 때 가장 먼저 줄을 선 사람이 기구를 먼저 타러 가고 늦게 온 사람들은 줄 서있는 사람들 뒤에 줄을 서지 바로 앞으로 가서 줄을 서면 안된다!! 큐가 이런 대기줄 개념이다. 먼저 넣은 것이 가장 먼저 나오기 떄문에 First In First Out(FIFO)라고도 한다. queue의 method 들을 살펴보면 push : 큐에 자료를 넣는 연산 pop : 큐에서 자료를 뺴는 연산 front : 큐의 가장 앞에있는 자료를 보는 연산 back : 큐의 가장 뒤에있는 자료를 보는 연산 empty : 큐가 비어있는지 아닌지를 알아보는 연산 size : 큐에 저장되어있는 자료의 개수를 알아보는 ..

스택 관련 문제들 계속 풀어보고 있다!! 백준 1874번 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 : 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First o..

Stack(스택)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저 나오기 때문에 last in first out (LIFO)라고도 한다. stack의 기본적인 기능은 push: 스택에 자료를 넣는 연산 pop: 스택에서 자료를 빼는 연산 top: 스택의 가장 위에 있는 자료를 보는 연산 empty: 스택이 비어있는지 아닌지를 알아보는 연산 size: 스택에 저장되어있는 자료의 개수 를 알아보는 연산 스택은 밑이 막혀있는 그릇 같은?? 구조라고 보면 되는데 우리가 먼저 넣은 음식이 맨 밑에 깔리는 거랑 같다고 보면 된다. 그래서 1 2 3 4 5 를 차례대로 스택 안에 넣었다고 가정하면 가장 먼저들어간 1이 가장 밑에 깔리고 제일 늦게 들어간 5가 스택의 맨 위에 있..