일상

풀이 이 문제는 언뜻 보면 이중 반복문을 이용해서 쉽게 풀 수 있을 것 같지만, 이렇게 할 경우 복잡도가 n^2가 되며, 시간 초과로 실패를 하게 된다. 따라서 이 문제는 스택을 이용해서 풀어야 한다. 스택을 이용할 때 핵심은, 스택에 저장되는 요소는 숫자가아니라 숫자를 나타내는 인덱스 라는 것이다. 풀이는 코드와 함께 보면 좋을 것 같아서 소스코드의 주석으로 달아놓았다. c++의 경우 std::vector를 마치 스택처럼 이용할 수 있기 때문에 vector를 이용하였다.#include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); int n; std::cin >> n; // 순열을 받을 array 선언 in..

풀이 제목에 나온대로 스택을 이용하여 풀어야 하는 문제이다. 문제에 대한 이해는 해당 문제 홈페이지의 힌트를 보면 어느정도 감이 잡히니 그것을 읽어보자. 이 문제의 경우 소스코드를 바탕으로 풀이하는게 좋을 것 같아서 먼저 소스코드를 첨부한다. 소스코드는 다음과 같다. #include #include #include template class Stack {private: std::vector s;public: void Push(S data) { s.push_back(data); } S Pop() { if (s.size() == 0) { return S(-1); } else { S temp = s[s.size() - 1]; s.pop_back(); return temp; } } int..

사실 이 문제의 풀이라기 보다는 이 문제에서 무조건 이용해야하는 에라토스테네스의 체 에 대한 풀이이다. 소수 관련 문제인데 시간제한이 타이트하면 무조건 에라토스테네스의 체를 생각하면 된다. 이 문제도 에라토스테네스의 체를 이용해서 풀어야 한다. 에타로스테네스의 체는 원하는 숫자의 범위 내에 소수를 판별할 수 있는 가장 빠른 방법이다. 가령 [1, 100] 범위 안의 소수를 알고 싶다면, 1에서 100까지의 숫자를 나열한 후 2의배수, 3의배수, 5의 배수, 7의 배수, ... , 10의 배수(100의 제곱근)에 대해서는 소수가 아니라고 표시하면 된다. 4의 배수, 6의 배수, 8의 배수, 9의 배수는 앞에서 2의배수, 3의배수에서 모두 아니라고 표시되므로 굳이 안해줘도 된다.  좀 더 일반적으로 정의하면..

풀이 풀이 과정은 크게 3단계로 나눠서(1). 문자열로 입력을 받고(2). 문자열 요소를 int 변환 후 각각의 요소에 대해 2진수를 구한 뒤(3). 첫번째 수가 1부터 나오게 만들기로 하였다. 먼저 코드를 써보면 #include #include int main() { std::string s; std::cin >> s; int oct_num; int binary[3] = { 0 }; for (int i = 0; i = 0) { binary[j] = 0; j--; } for (int k = 0; k  여기서 애먹은 단계는 2단계여서 2단계 풀이에 대해서만 좀 더 써 보면, 우선 2단계 구현의 경우 첫번째 for문과..

풀이 예를 들어, 2층 3호의 거주민 수를 알고 싶다면 0층의 1호 ~ 3호의 거주민 수, 1층의 1호 ~ 3호 거주민 수를 알고 있으면 된다. 즉, k층의 n호의 거주민 수를 알고 싶다면 (k-1)층 까지의 1호 ~ n호 거주민 수를 알고 있으면 된다. 먼저, 동적할당으로 n 사이즈의 배열을 선언 후, 0층의 1호(배열 index : 0)에서 n호 (배열 index : 1) 의 거주민 수를 초기화 한다. 이후 1층부터 K층까지 차례대로 거주민 수를 계산하게 된다 다이나믹 프로그래밍이라는 힌트를 알게되면 무난하게 풀 수 있는 문제이다. #include int main() { int t; //test case num std::cin >> t; int k, n; // k : floor, n : room nu..

풀이 과정 벌집이 생성되는 과정을 풀어보면 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, ... , 61 1에서 6을 더한 7까지가 거리가 2가 되고 7에서 6의 2배인 12를 더한 19까지가 거리가 3이 되며 19에서 6의 3배인 18을 더한 37까지의 거리가 4가 된다. 이 규칙에 따라서 코딩을 진행하면 된다. 먼저 반복문에 주요한 변수는 num과 i이다. num은 특정 거리에서 맨 마지막 수를 나타낸다고 생각하면 된다. 따라서 계속 누적을 해줘야한다는 것이 핵심이다. i는 거리를 나타낸다고 생..

풀이 - 먼저 총 꼭지점의 개수는 (사각형의 한 면의 꼭지점의 개수) x (사각형의 한 면의 꼭지점의 개수)이다 - 점 하나를 추가한다고 할 때마다 사각형의 한 면의 꼭지점의 개수는 초기값이 1이고 공비가 2인 공비수열의 형태로 늘어난다 - 따라서 이 규칙을 코딩에 적용하면 끝! #include //맨 왼쪽 면의 꼭지 점 개수는 2, 3, 5, 9, 17, 33 순으로 늘어나는데 //이것의 증가폭을 따져보면 1, 2, 4, 8, 16.. 즉 2의 거듭제곱 순으로 늘어난다 //즉 initial value가 1이고 common_ratio가 2인 등비수열 int main() { int n; std::cin >> n; int init = 2; int add = 1; int common_ratio = 1; for..

풀이 사실 문제만 본다면 소스코드를 생각하는것이 쉽지 않다. 이 문제는 이차원 배열을 이용하면 간단하게 풀 수 있는 문제다. 먼저 (100, 100) 사이즈의 0으로 초기화 된 이차원 배열을 선언 후 입력받은 범위에 있는 배열의 element를 1로 만들어준 뒤 이차원 배열에 있는 1 값을 모두 더해주면 답이 나온다. 제출코드 #include int main() { int plate[100][100] = { 0 }; int paper_num; std::cin >> paper_num; for (int i = 0; i > x >> y; for (int j = x; j < x + 10; j++) { for (int k = y; k < y ..

풀이 문자열의 배열을 이용하여 푸는 문제다. 1). 문자열은 5개를 입력받는 것이 디폴트이기 때문에 먼저 반복문을 이용하여 문자열을 생성하였다. 이때 문자열들 중 가장 긴 길이를 측정한다. 2). 반복문에 사용할 k라는 변수를 초기화한다. 먼저 while문을 선언하여 k가 1)에서 구한 최대 문자열 길이 값을 넘으면 반복문은 종료된다. k라는 변수는 이차원 배열의 두 번째 element의 접근에 쓰인다 3). while문 안에 for문을 선언한다. 이때 정의되는 변수는 이차원 배열의 첫 번째 element를 접근하는데 쓰인다 4). 만약 어떤 문자열의 길이 -1 이 k보다 작다면 이때는 해당 배열값에 아무값도 없기 때문에 출력하지 않는다. #include #include int main() { std::..

푸는데 시간이 꽤 걸린 예제라서 관련 포스팅을 진행하려고 한다. 처음 제출 코드는 아래와 같다 #include /* c= c- dz= d- lj nj s= z= c : 99 = : 61 - : 45 d : 100 z : 122 l : 108 j : 106 n : 110 s : 115 z : 122 앞에 나오는 알파벳 c : -, = case 1 d : z, -, z= case 2 z : = case 3 l : j case 4 n : j case 5 s : = case 6 */ int main() { std::string s; std::cin >> s; int i = 0; int count = 0; while (i < s.length() - 1) { if (int(s[i]) == 99) { //case1 ..