Jonyo Programming

[BOJ 11505(G1)리뷰] N개의 값이 1번 index부터 차례대로 주어진다. 그 후에 명령을 입력받는데 "1 a b"의 형태라면 a를 b라는 수로 바꿔야하고, "2 a b"의 형태라면 a번 index부터 b번 index까지의 곱을 출력해야 한다. 값을 update하는 작업이 있으므로 단순히 구간의 곱을 저장하는 것으로는 시간내에 해결 할 수 없다. 따라서 값을 update하고 구하는 과정을 O(logN)에 수행할 수 있는 세그먼트 트리 자료구조를 이용했다. 일반적으론 구간의 합을 세그먼트 트리 구조로 저장하지만, 이번 문제는 구간의 곱을 저장해주면 된다. 따라서 값에 영향을 주지 않도록 비어있는 노드는 1로 초기화 해주어야하며, 값을 update할때는 botoom-up방식으로 구현 하는 것이 깔끔..

[BOJ 5670(P3)리뷰] 저장된 단어를 기준으로 자판 자동완성(?) 기능을 만들어야 한다. 예를들어, hello라는 단어가 저장되어 있다면 he만 입력해도 hello라는 단어가 완성되어야 한다. 하지만 h로 시작하는 단어가 2개 이상이라면 자동완성이 되어서는 안되고 사용자로부터 입력을 받아야 한다. 즉, 단어 사전에 hello 와 heaven만 저장되어 있다면 h를 누르는 순간 'e'가 자동으로 입력되어야 하고 (h로 시작하는 단어는 모두 뒤에 e가 붙으므로) 그 후에는 사용자로부터 입력을 받아야 한다. 그리고 만약 he가 입력된 상태에서 'l'을 입력하게 되면 그 후에는 존재하는 단어가 1개이므로 'hello'까지 자동완성 되어야 한다. 입력으로 휴대폰에 저장된 단어의 목록이 주어졌을 때, 각각의..

[BOJ 9202(P5)리뷰] 간단해 보이지만 간단하지 않은 문제다. 사용자로 부터 미리 N개의 단어를 입력받는다. 그리고 4X4크기의 보드를 입력받는다. 이 보드에서 가로,세로,대각선으로 이동하며 만들 수 있는 단어의 개수, 단어의 총 점수(단어의 길이마다 점수가 있다.), 가장 긴 단어를 출력해야 한다. 보드에서 단어를 찾는것 + 미리 입력받은 N개(최대 30만개) 의 단어목록에 있는지 확인하는 작업을 완전탐색으로 하려면 내가 늙어 죽을때 까지 돌려도 찾기가 힘들것이다. 따라서 이 문제를 해결하기 위해서는 "트라이"라는 자료구조에 대해 알아야 한다. 트라이는 위 그림과 같은 구조를 갖고있다. 각각의 노드는 객체로 이루어져있으며 객체는 a~z 또는 A~Z의 26개의 동일한 객체를 갖는 구조로 되어있다...

[BOJ 2243(P5)리뷰] 세그먼트 트리를 응용하는 문제다. 사탕상자에서 사탕을 넣거나 뺄 수 있고, 동생에게 N번째로 맛있는 사탕을 줘야할 때도 있다. 사탕의 맛은 1부터 100만이다. 이걸 배열로 기록하여 값을 업데이트 한다면 시간복잡도O(N^2)으로 시간초가가 나게 된다. 따라서 업데이트를 O(logN)에 가능하게 하여 최종적으로 O(NlogN)으로 풀어야 정답처리를 받을 수 있다. 일반적으로 세그먼트 트리에는 구간의 합을 저장한다. 가장 리프노트에는 본래의 값이 들어있고, 리프노드에서 부모노드로 올라갈 수록 자식노드의 합들을 저장하며 루트노드까지 올라간다. 최종적으로 루트노드에는 전체범위의 합이 저장되어 있다. 이 문제는 이러한 구조를 갖는 세그먼트 트리를 응용하여 풀어야 하는 문제다. 사탕의..

[BOJ 11003(P5)리뷰] 문제는 매우 간단하다. (하지만 푸는건 간단하지 않음 ..) N개의 수와 정수 L이 주어진다. 각각의 원소마다 자신의 앞과 자신의 앞을 포함하여 L개의 원소 중 최솟값을 출력하면 된다. 예를들어 N=8이고 [1,5,2,3,6,2,3,7] L이 3이라면 1 -> 최솟값 : 1 1,5 -> 최솟값 : 1 1,5,2 -> 최솟값 : 1 5,2,3 -> 최솟값 : 2 2,3,6 -> 최솟값 : 2 3,6,2 -> 최솟값 : 2 이런식으로 최솟값을 출력하면된다. 창틀을 정해놓고 그 창틀을 조금씩 이동하는것처럼 보이기도 하여 슬라이딩 윈도우라고도 한다. 일단 각각의 원소마다 자신의 앞에 있는 수를 탐색하는 O(N^2)으로는 절대 안풀리고 힙이나 BST를 이용한 O(NlogN)으로도 ..

[BOJ 2517(P4)리뷰] 이 문제는 Inversion Count 알고리즘을 이용하여 해결할 수 있다. 문제를 잘 읽어보자. 각각의 선수들은 달리기를 하고 있는데, 자신보다 앞에 있는 선수보다 실력이 좋으면 그 선수를 따라잡을 수 있다고 한다. 이 때 각각의 선수들의 최선의 등수를 구해야 한다. 즉, 문제를 쉽게 풀자면 각각의 선수마다 자신의 앞에있는 선수 중 자신보다 능력치가 낮은 선수가 몇명인지 구하여 자신이 그 선수들을 따라잡았을 때의 최종등수가 몇등이냐를 구해야 하는 문제이다. 가장 쉬운 풀이로는 각각의 선수마다 앞의 있는 선수들을 탐색하는 O(N^2)풀이를 떠올리겠지만 이 풀이로는 시간초과를 맞게된다. 더 효율적인 알고리즘이 필요하다. 이 때 사용한 방법이 inversion count다. 머..

배열에 [1,3,2,5,7,6] 라는 값이 들어있을 때 자신의 앞에 있는 수 중에 자신보다 크기가 큰 수의 갯수를 찾으려면 어떻게 해야할까? 즉, i A[j] 를 만족하는 갯수를 찾는것이다. 1은 맨 앞에 있으므로 1보다 앞에 있는 수 중 자신보다 큰 수는 없다. 3은 두번째에 위치하지만 앞에 있는 수가 자신보다 작으므로 자신보다 큰 수는 없다. 2는 자신의 앞에 자신보다 큰 3이라는 숫자가 있다. 이런식으로 배열 원소의 각각의 위치에서 자신보다 "앞에 있는" 수 중에 자신보다 "큰" 수를 찾고 싶을때 쓰인다. 쉽게 떠올릴 수 있는 가장 일반적인 방법은 이중for문을 돌면서 각각의 원소마다 자신보다 큰 수의 갯수를 찾으면 될것이다. 그러나 이건 O(N^2)의 시간복잡도를 가지므로..

[BOJ 7453(G2)리뷰] 이전에 풀었던 BOJ : 2143 두 배열의 합 문제와 비슷한 유형의 문제다. 다만 배열의 개수가 2개에서 4개가 되었고, 이번엔 4개의 배열의 합이 0인 쌍들의 개수를 구해야 한다. 과정은 지난 문제와 비슷하다. 다만 조금 로직을 다르게 했다. 일단 먼저 A,B,C,D배열을 AB배열의 두 배열의 합으로 합치고, CD배열의 두 배열의 합으로 합쳤다. 그리고 마찬가지로 오름차순으로 정렬을 해줬다. 이제 이 두 배열에는 A,B배열을 서로 더한값과 B,C배열을 서로 더한값이 오름차순으로 정렬되어 있다. 처음엔 이 상태에서 투 포인터를 이용해 풀었지만 시간초과를 맞았다. map에 갯수를 세는 과정에서 발생한것이라 생각된다. 그래서 이번엔 합이 0인 쌍들을 구한다는 특성을 이용하여 ..

[BOJ 2143(G3)리뷰] 투 포인터를 응용해야 하는 문제이다. 문제에서 배열이 두개가 주어지고, 두개의 배열을 이용하여 만들 수 있는 합 중 T를 만족하는 경우의 수를 찾아야 한다. 완전탐색하는 방법으로는 시간초과를 맞게 되므로 투포인터 알고리즘을 이용해야 한다. 투 포인터 알고리즘을 이용하기 위하여 A와 B배열에 대해 각각의 구간합을 저장하는 사전작업을 했다. 즉, 1,3,2,1 배열이라면 1 4 6 7 3 5 6 2 3 1 라는 별도의 배열을 만든다. 그리고 이렇게 만들어진 두개의 배열을 각각 오름차순으로 정렬 한 후에 하나의 배열은 시작부터, 하나의 배열을 끝부터 시작한다. 이미 이 배열에 구간의 합에 대한 경우의 수가 들어 있으니 이 두개의 배열의 합이 T를 만족하는 개수를 찾으면 된다. 다..

[BOJ 1039(G3)리뷰] 굉장히 어려웠던 문제다. 처음엔 이걸 어떻게 BFS로 풀라는 건지 한참 고민을 했다. 계속 고민을 하다보니 그냥 모든 경우에 대하여 BFS를 돌리면 되는 간단한 문제인가? 라는 생각이 들어 바로 코딩을 했지만 계속 메모리초과&시간초과가 났다. 시간초과가 났던 이유는 너무나 당연했다. 두개의 값을 바꾸는 과정에서 중복되는 값이 큐에 푸쉬되는 현상이 반드시 일어 날 수있고, K가 클수록 시간복잡도 측면에서 매우 큰 손해를 보게 된다. 따라서 중복된 값을 큐에 넣지않도록 별도의 처리를 해줘야 한다. 다만 이때 각각의 연산마다 중복처리를 하는것을 독립적으로 계산해야 한다. 즉, 16375 에서 61375가 되고 다시 16375가 될 수 있는것이다. 각각의 연산횟수마다 독립적으로 처..