펭로그

문제링크 : https://noj.am/6603 N개의 원소를 가지는 집합에서 K개를 고르는 조합(Combination) 문제로 STL의 permutation을 사용하면 쉽게 풀 수 있다.algorithm 헤더에 있는 next_permutation()과 prev_permutation()으로 순열을 구할 수 있다.[1, 2, 3, 4]를 next_permutation()을 사용하면[1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] ..... 이런 식으로 사전 순서대로 순열이 적용된다.prev_permutation()은 그 반대라고 볼 수 있다. 그렇다면 조합을 사용하려면 어떻게 해야할까?[1, 1, 0, 0]을 prev_permutation()으로 돌려보면 아래와 ..

문제링크 : https://noj.am/9935 요즘 알고리즘 테스트 문제들이 파싱 문제들이 하도 많이 나와서 연습해볼겸 별 의미는 없지만 string stream을 사용하여 풀어보았다.string stream을 통하여 입력된 문자열이 폭발 문자열의 '마지막 문자'에 해당할 경우 이전에 입력되었던 문자열이 폭발 문자열과 일치하는지 체크하는 방법으로 풀이했다. 본 풀이법은 스택을 사용한 풀이법이라 할 수 있다. 예제에서는 "C4"가 폭발 문자열이다.아래의 조건에서 '4'를 찾았다면 문자열 탐색이 실행된다.1if (s == bomb.back())cs 먼저 idx 변수를 폭발 문자열 크기만큼 뺀 인덱스로 초기화 시켜준다.폭발 문자열의 맨 앞인 'C'에 해당하는 값이다.123int idx = result.siz..

문제링크 : https://noj.am/9095 어떤 숫자 N을 1, 2, 3 더하기로 나타내는 방법은 다음과 같다.[1] - 1개1 [2] - 2개1+1 → [1]+12 [3] - 4개1+2 → [1]+21+1+1, 2+1 → [2]+13 [4] - 7개 (1+2+4)1+3 : [1]+3 → [1] + 31+1+2, 2+2 → [2] + 21+2+1, 1+1+1+1, 2+1+1, 3+1 → [3] + 1 [5] - 13개 (2+4+7)1+1+3, 2+3 → [2] + 31+2+2, 1+1+1+2, 2+1, 3+2 → [3] + 21+3+1, 1+1+2+1, 2+2+1, 1+2+1+1, 1+1+1+1+1, 2+1+1+1, 3+1+1 → [4] + 1 위와 같이 시뮬레이션을 해보면 DP[N] = DP[N-..

문제링크 : https://noj.am/2583 단순 DFS/BFS 문제이다.계산하기 편하게 (1,1)~(N,M)의 영역을 사용한다.초기에 테두리를 방문한 것으로 체크하고 내부를 미방문한 상태로 초기화 시키면 ▣ Y >> X >> K; // true : 방문, false : 미방문 // 테두리를 방문한 것으로 만들고 내부는 미방문 상태로 초기화 arr = vector(X + 2, vector(Y + 2, true)); for (int i = 1; i > y1 >> x2 >> y2; for (int x = x1 + 1; x

문제링크 : http://codeforces.com/contest/1059 C. Sequence Transformation 각 숫자들을 인수분해 하면 소수들의 곱으로 이루어진다.입력 사이즈가 100만이기 때문에 100만의 제곱근 만큼인 1000까지의 소수를 구하고 그 소수들 중에서 가장 많은 배수들을 가지고 있는 소수를 추려내고 나머지 모든 수를 1로 출력, 그 소수의 제곱수가 아닌 숫자를 그 소수로 출력, 소수의 제곱수를 출력 하는 식으로 문제를 접근했는데.. 답은 맞게 나오겠지만 메모리 공간이 분명 초과되는듯 하다. 기존엔 문제를 이렇게 풀었으나 출력해서 규칙을 보니.. 2의 배수만 신경쓰면 되는 것을 발견했다.3을 제외하고 전부 2로 출력되었으니 말이다.. 12345678910111213141516..

문제링크 : http://codeforces.com/contest/1059 A. Cashier 단순 구현문제로 중간에 비는 시간에 담배탐을 할 수 있는 시간이 있는지 체크하여 누적하고 업무가 끝나고 남은 시간도 담배탐을 할 수 있는 만큼 더해준다. 12345678910111213141516171819202122232425262728293031323334353637// Codeforces Round #514 (Div. 2)// A. Cahier#include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", std..

문제링크 : https://noj.am/13458 단순 구현 문제인데 정답률이 25%대로 낮은 문제이다.그 이유는 출력 자료형을 다들 고려하지 않아서 그런 것 같다.최대로 나올 수 있는 값이 1,000,000 * 1,000,000이기 때문에 long long 타입을 사용해야한다. 1234567891011121314151617181920212223242526272829303132// BOJ 13458 시험 감독#include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);// freopen("../input.txt", "r", stdin); int num, main, su..

문제링크 : https://boj.am/1991 문제에서 입력은 A~Z로만 한정되어 있다. 이러한 특성 덕분에 간단한 형태로 트리를 구현할 수 있다.char 형태의 A(65) ~ Z(90)에서 A(65)씩 빼주면 A(0) ~ Z(25)로 표현할 수 있기 때문이다.따라서, 인덱스 번호 자체가 노드에 들어있는 문자를 의미하는 것이기 때문에 2개의 배열 만으로도 트리의 구현이 가능하다. 현재 노드를 V, 좌측 자식 노드를 L, 우측 자식노드를 R이라고 한다면전위순회는 V-L-R 순서로중위순회는 L-V-R 순서로후위순회는 L-R-V 순서로 순회하게 된다. 스택을 이용하여 구현을 하려고 시도해봤으나 너무 복잡하여 재귀로 구현했다. 1234567891011121314151617181920212223242526272..

문제링크 : https://noj.am/8916 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071// BOJ 8916 이진 검색 트리#include using namespace std; long long comb(int n, int r) { // nCr r = n - r > r ? r : n - r; long long result = 1; for (int i = 0; i tc; while (tc--) { int num, input; vector tree(1); cin >> num; while(num--) { int i..

문제링크 : https://noj.am/11403 전형적인 BFS / DFS 문제그냥 풀면 된다. 자기 자신노드로 돌아오는 경우가 있기 때문에 맨 처음은 방문체크를 하지 않았다.인접리스트는 graph[0] = {1, 3, 5, 6, 7} 이런 형태로 저장된다. 현재 노드에서 해당 노드로 갈 수 있으면 저장된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253// BOJ 11403 경로 찾기#include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cou..