Jonyo Programming

[BOJ 2252(G2)리뷰] N명의 학생들을 키 순서대로 줄 세우려고한다. 이 때 학생들의 키를 알지 못하여 두 학생의 키를 비교한 결과를 통해 정렬하려고 한다. 예를들어, "1번학생이 3번보다 크고 3번학생이 2번보다 크다" 라고 한다면 이 세 학생의 키 순서는 1>3>2 가 될 것이다. 학생들의 정보가 주어졌을때 학생들의 키 순서대로 출력을 해야 한다. 이 문제는 위상정렬이라는 알고리즘을 통하여 해결할 수 있다. 주어진 정보를 그래프로 구성해보자. 만약 "1번학생이 3번보다 크다"라는 정보가 있다면 (1) > N >> M; for (int i = 0; i > a >> b; adj[a].push_back(b); indegree[b]++; } //inde..

[BOJ 14476(G2)리뷰] N개의 정수가 주어지고 그 중 하나를 뺐을때 남은 정수들의 최소공배수가 최대가 되는 경우를 구해야 한다. 예를들어 [8,12,24,36,48]이라는 정수가 주어졌을 때, 8을 뺀다면 나머지 [12,24,36,48]의 최대공약수가 12로 가장 크다. N의 범위는 4 [12,48] -> [12,12,48] 이런식으로 값을 채워나가게 된다. 그렇다면 이제 [8,12,24,36,48]의 배열에서 가운데에 있는 24라는 값을 뺐을때의 최대 공약수를 구해보자. 24의 index를 3이라 했을때 GCD(LEFT GCD[2],RIGHT[4])가 24를 제외한 나머지 수들의 최대공약수가 되게 된다. 이 알고리즘을 이용하여 N개의 수들을 하나씩 빼가며 최대공약수를 확인하고, 최대공약수가 최..

[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인 쌍들을 구한다는 특성을 이용하여 ..