펭로그

문제링크 : https://noj.am/14500 1. 모든 경우의 수를 시뮬레이션하여 풀기테트로미노가 나올 수 있는 모든 상황을 시뮬레이션해서 문제를 푸는 방법이다.문제에서 조건을 살펴보면N*M은 최대 500*500 = 250,000테트로미노가 나올 수 있는 모양의 가지 수 = 19가지 250,000 * 19 = 4,750,000번 이므로 1억번을 초과하지 않는다.무식하게 한 좌표를 기준으로 19번의 테트로미노의 상태 모두를 탐색하는 방법으로 푸는게 시간복잡도 면에서는 가장 효율적이다. 다만, 이 방법으로 풀 경우 모든 경우, 숫자를 한개라도 틀리게 적었을 경우 실수하기가 매우 쉽다. 123456789101112131415161718192021222324252627282930313233343536373..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 가장 긴 등산로를 만드는 문제로 시작점은 가장 높은 봉우리에서 시작한다.입력을 받을 때 가장 높은 숫자를 highest 변수에 저장하고완전 탐색을 돌리는듯 하면서 값이 highest일 때만 dfs를 돌려서 탐색한다.71727374757677// 값 저장for (int i = 1; i arr[i][j]; highest = max(highest, arr[i][j]); }}Colored by Color Scriptercs A->B 까지 가는 등산로는 A->C->D->B로 돌아서 가는 식의 등산로로 표현할 수도 있기 때문에A-..

문제링크 : 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/1759 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192// BOJ 1759 암호 만들기#include #include #include using namespace std; vector arr; // 전체 문자vector mo; // 모음vector answer; // 정답 문자vector expt; // 검색 제외vector result; // 출력int size, inp; // 문자열 길이, 입력 크..