펭로그

문제링크 : https://noj.am/16236 BFS로 그냥 풀면 간단한 문제일 줄 알았는데 개인적으로는 약간 고민을 많이 했던 문제이다.아기 상어가 물고기를 먹을 때 먹을 수 있는 물고기 중에서 가장 가까운 아무거나 먹는게 아니라 가장 위, 가장 왼쪽에 있는 것을 먹어야 한다는 까다로운 조건이 붙기 때문이다.이를 해결하기 위하여 우선순위 큐 + BFS를 사용하여 해결하였다. BFS를 위해 필요한 큐를 우선순위 큐로 사용하였고큐에 담길 데이터는 연산자 오버로딩을 통하여 아래와 같이 min heap이 구성되는 방식이다.① BFS 레벨이 작은 순서 (상어의 이동 거리)② x의 좌표가 작은 순서③ y의 좌표가 작은 순서 123456789101112131415161718192021222324252627282..

문제링크 : 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/14891문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH 톱니바퀴가 회전하게 되면 각각의 인덱스 위치가 변동된다. 어떤 톱니바퀴의 인덱스가 다음과 같다면0 1 2 3 4 5 6 7 시계방향으로 회전시7 1 2 3 4 5 6 반시계방향으로 회전시1 2 3 4 5 6 0 이렇게 순서가 바뀌므로 rot[] 에 회전이 얼마나 되었는지를 저장해준다.8바퀴를 회전하게 되면 제자리가 되므로 8로 나눈 값을 저장해주면 된다.10111213// 톱니바퀴 회전void rotat(int idx, int dir) { rot[idx] = (rot[id..

문제링크 : https://noj.am/14890문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH (이전 노드 - 현재 노드)의 높이 차이가 +1일 경우 : 내리막(이전 노드 - 현재 노드)의 높이 차이가 -1일 경우 : 오르막 내리막 경사로가 건설되려면 앞으로 len 만큼의 길이가 확보되어야 하고오르막 경사로가 건설되려면 이전에 이미 len 만큼의 길이가 확보되었어야 한다. 내리막 + 오르막 경사로가 건설되어야 할 경우에도 그 사이 길이가 len 만큼 확보되어야 한다. 공간의 확보를 위해선 높이의 차이가 같은 구간이 몇개인지 카운트를 해가면서 계산하면 된다. 1234..

문제링크 : https://noj.am/5639 이진 트리를 구성하고 있는 각 노드는 다음과 같이 표현한다.V - 부모 노드L - 왼쪽 자식 노드R - 오른쪽 자식 노드 이진 트리의 순회 방식은 다음과 같다.전위 순회 : V-L-R중위 순회 : L-V-R후위 순회 : L-R-V 문제에서 주어진 다음 조건을 보면 힌트를 유추할 수 있다. 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 입력으로 전위순회를 시행했을 때의 결과가 주어진다고 했기 때문에 위의 원리를 그대로 적용해보면 각 노드별 서브트리를 구할 수..

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