숫자를 크게 보면, S + 1을 기준으로 나머지가 0인 3개의 부분과, 나머지가 1이 아닌 2개의 부분으로 구획 가능하다. 이것을 기준으로 or 연산자를 활용해서 쉽게 계산할 수는 있다. (다만, 귀찮아서 그냥 0~9까지 케이스를 각각 저장해두고 필요할때마다 꺼내 쓰는 방식을 채택하였다.) 매우 비효율적인 코드이지만 그냥 넘어가자.(귀찮다.) #include #include #include #include #include using namespace std; int main(void){ int S; string N; cin >> S >> N; char zero_store[23][12]; char one_store[23][12]; char two_store[23][12]; char three_store[2..

사실.. 처음 풀 때 순간적으로 착각하여 오래 풀게 되었다. 단순히 옮기는 것이므로, 각 component에 해당하는 숫자가 그대로 노출되어 있는 부분이 반드시 존재할 것으로 착각하였으나 그렇지 않은 부분도 있었다. 대표적인 예시가 3 4 1 1 1 2 3 4 0 5 7 9 11 4 9 15 17 19 8 0 9 10 11 12 이다. 이 경우에는 6, 7 부분이 직접적으로 나오지는 않는다. 따라서 풀이방법은 다음과 같다. 1. 덧셈이 아니라 직접적으로 노출된 부분을 store한다. (단, 해당 배열의 default 상태를 -1로 두어 저장된 것인지 아닌지를 구분한다.) 2. 겹치는 부분을 기준으로 찾되, 더해진 2개의 index값 중 default 상태에서 변화된 부분이 있으면 그것을 통해 나머지 in..

처음에 이 문제를 보고 자연스럽게 생각나는 풀이방법은 이중 for loop를 활용하여 계속해서 해당 결과값들을 더해나가는 것이다. 그런데, 그런 방식으로 풀게 될 경우 데이터가 10만개이므로 시간 복잡도가 대략 O(n^3)가 나온다. (시그마 계산을 하게 되면 이는 쉽게 증명할 수 있다.) 그러면 최악의 경우를 고민해보았을 때 시간초과가 난다는 사실을 알 수 있다. 그렇기에 다른 방법을 강구해야 한다. 잘 생각해보면 결과적으로 하나의 숫자는 다른 모든 숫자와 곱해지는 형태이므로 전체 sum에서 자기 자신을 뺀 만큼이 곱해지게 되는 양상으로 진행되게 된다.(결합법칙 정도로 이해하면 충분하다.) 다만, 중복되는 것을 감안해서 마지막에 1/2처리만 해주면 된다. 일종의 대각선 갯수 구하는 알고리즘이랑 느낌이 ..

어렵지는 않은데, 효율적으로 방법을 고안하는데 시간을 많이 쏟았다. 시계 방향으로 주어지는 경우에는 기본적으로 index와 방향을 매칭시키는 것이 좋다. 예를 들어 북쪽 방향으로 이동하는 것을 0, 동쪽은 1, 남쪽은 2, 서쪽은 3으로 매칭시키게 되면 회전시킨때마다 방향 + 1로 취급해주면 된다. (물론 3의 경우만 따로 0으로 취급해주면 된다.) 막힌 것을 따로 체크해주면서 진행해주면 된다. 다만, direction별로 계속 if문이 들어가므로 함수를 따로 잡는 것이 유리하다. #include #include #include using namespace std; int m, n; int change_num = 0; int count_store = 1; // 방향 바꿔주는 함수 int change_di..

1967과 동일한 알고리즘으로 접근해주면 된다. 구현 방법에 대해서 잘 기억해두도록 하자. #include #include #include #include using namespace std; struct node{ vector len_store; }; int visited[100001] = {0}; int end_point; int result; void tree_checker(node *data_store, int start, int length){ if(visited[start] != 0) return; visited[start] = 1; if(result < length){ end_point = start; result = length; } for(int i = 0; i < data_store[s..

종만북에서 본 적이 있는 유형이라 쉽게 푼 편이다. 이분트리 탐색의 경우에는 재귀를 활용해줘서 처리해주면 된다. 부분과 전체를 보면서 코드를 구현할 수 있어야 한다. 이 문제를 요약하면 전위 순회를 후위 순회로 돌려야하는 것이다. 이분트리를 보면 각 노드를 기준으로 왼쪽은 자신보다 더 작고, 오른쪽은 자신보다 크다. 이러한 성질은 전체적으로 보아도 성립하고 최소 단위로 보아도 성립한다. 즉, 전위 순회를 한 데이터를 기준으로 자신보다 큰 숫자가 나올 때 그것이 오른쪽 노드의 시작을 의미함을 이해할 수 있다. 그러므로 자신보다 큰 숫자가 어느 시점에 나오는지를 확인하고 그것을 기준으로 왼쪽과 오른쪽 노드를 구분하면 된다. 후위 순회의 경우, 이 과정에서 자식 노드의 왼쪽과 오른쪽을 출력하고 자기자신을 출력..

이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다. 처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다. 하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.) 즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다. 해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; struct node{ vector path_store; }; int checker(node *data_store, in..

대표적인 전위 순회, 중위 순회, 후위 순회를 활용한 탐색이다. 이진트리이므로 구조체(클래스)를 활용하여 좌/우 노드를 저장하고 재귀를 활용하여 방문해주면 된다. 아래 코드들을 익숙하게 활용할 수 있도록 반복할 것 #include #include #include #include #include #include using namespace std; struct node{ char left; char right; }; void first_cycle(node *data_store, char start){ int check_num = start - 'A'; cout > parent >> left >> right; data_store[parent - 'A'].left = left; data_store[parent..