펭로그

문제링크 : 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/16234 완탐 + DFS/BFS 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 // BOJ 16234 인구 이동#include #include using namespace std; int dx[] = {0, 0, -1, 1};int dy[] = {-1, 1, 0, 0}; struct node { int x, y;}; int N; // 크기int L, R; //..

문제링크 : https://noj.am/14888문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH DFS를 이용하여 완전탐색을 시행한 브루트포스 문제이다.각 시행 마다 + - * / 연산 모두를 다음 탐색에서 시행한다.구조를 간단하게 하기 위하여 구조체 안에 생성자를 통해서 다음 노드의 구조체를 만들어준다.이 때, 입력받은 연산이 무엇인지를 확인하여 + - * / 의 연산을 구분해서 데이터를 새로 만들어준다. 재귀 호출 시마다 4번의 추가 호출이 있기 때문에 시간 복잡도는 O(4^N)이다.문제에서 N은 11까지라는 조건이 있으므로 4^11 = 4,194,304 이다.최대 1억..

문제링크 : 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/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

문제링크 : 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..

문제링크 : 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; // 문자열 길이, 입력 크..

문제링크 : https://boj.kr/11559 1. 블럭은 4개 이상 모였을 때 터짐2. 동시에 터지는 것은 하나의 연쇄 단계임3. 한 연쇄 단계에 블럭이 터진 이후 중력에 의해 블럭이 아래로 내려감 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124// BOJ 11559 Puyo Pu..

문제링크 : https://boj.kr/2468 흰색으로 연결된 부분들의 갯수를 세는 문제다.갯수를 세는 것은 DFS로 풀면 되는데.. 문제는 1~100까지의 비 내리는 높이들을 하나 하나 다 계산해봐서 영역이 가장 많은 것을 구하는 것이다.어떻게 해야 효율적으로 구할 수 있을까 생각해봤는데.. 일단 풀었다.1~100까지의 횟수는 그리 많은 횟수가 아니라 시간 복잡도 상으로도 O(1)에 해당하기 때문에..그래서 1~100 까지의 모든 높이마다 각각 dfs를 그냥 돌렸는데 시간초과도 나지 않고 풀렸다. 이미 풀렸기 때문에 여기서 시간을 더 줄이는 효율적인 방법은 생각해보지 않았다.혹시나 해서 입력 받을때 최소 높이, 최대 높이를 추가로 체크해서 풀었는데 어짜피 시간은 똑같이 나왔다. 별로 의미가 없는듯 차..