펭로그

문제링크 : https://noj.am/1057 문제의 조건에서 지민과 한수가 둘이 만나기 전까지는 무조건 이긴다고 하였다.따라서 문제에서 나온 조건대로 하면 '만약 서로 대결하지 않을 때는 -1을 출력한다.'은 절대로 나올 수 없기 때문에 무시해도 된다. 두 사람이 만날 수 있는 조건은 A와 B가 각각 2n-1과 2n 이어야 하는 조건이다.계산을 편하게 하기 위해서 그냥 A, B를 작은 순서대로 정렬하고 A가 홀수이고 A-B의 차가 1이면 정답으로 출력하도록 했다. 두 사람이 각 라운드에서 만나지 못한다면 div( ) 함수를 통하여 입력값을 절반으로 나누어주면서 정답을 찾아가면 된다.절반씩 계속 나누기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 보일 것이다. 1234567891011121314..

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

문제링크 : 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. 중위 표기법 수식을 후위 표기법 수식으로 변..

문제링크 : 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 문제에서 주어진 다음 조건을 보면 힌트를 유추할 수 있다. 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 입력으로 전위순회를 시행했을 때의 결과가 주어진다고 했기 때문에 위의 원리를 그대로 적용해보면 각 노드별 서브트리를 구할 수..