펭로그

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

문제링크 : 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/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://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV184uV6I70CFAZN 어느 회사 오프라인 코딩 테스트 문제로 문자열 계산기가 나왔었다.중위표기를 후위표기법로 바꿔서 풀면 풀린다는 개념은 알고 있었지만 당시엔 제대로 생각이 안나서 시간만 허비했었다....시험은 이미 끝났지만 그래도 다시 한번 풀어보기로 했다. 사칙연산을 할 때 연산 우선 순위는 다음과 같다. 1. 괄호를 먼저 계산하라.2. 곱셈 또는 나눗셈3. 덧셈 또는 뺄셈 하지만, 이는 사람이 쉽게 이해할 수 있는 형태의 논리이며 컴퓨터가 이해할 수 있는 논리로 바꾸면 다음과 같다. - Step1. 중위 표기법 수식을 후위 표기법 수식으로 변..

윈도우에서 MinGW를 이용하여 gcc 컴파일러를 이용할 때 한글을 출력하게 되면 깨지는 현상이 발생한다. 이는 MinGW + gcc 로 설치된 기본 환경에서 한글 캐릭터셋을 지원하지 않기 때문이다. CLion을 윈도우에서 사용하면 위 그림과 같이 한글이 깨져서 출력되는 것을 알 수 있다. 이를 해결하려면 캐릭터 셋을 euc-kr 또는 CP949와 같은 형태로 바꿔줘야 한다. 1set(CMAKE_CXX_FLAGS "-fexec-charset=CP949")cs 한글 문자로 인코딩 방법을 바꾸기 위해 CMakeLists.txt 파일에 위와 같이 CP949 캐릭터 셋을 출력하기 위한 문구를 입력하고 Reload changes 버튼을 누르면 간단하게 한글 깨짐 현상을 해결할 수 있다. 캐릭터 셋을 euc-kr로..

문제링크 : 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()으로 돌려보면 아래와 ..