프로그래민👨‍💻

LIS의 대표적인 예제 문제이다. LIS를 구현함에 있어 크게 n^2의 시간복잡도를 가지는 dp, nlogn의 시간복잡도를 가지는 lower_bound가 있다. 이 문제 같은 경우는 n의 최대 크기가 1000이기에 dp를 이용하여 풀어보았다. dp를 이용하여 푸는 경우 LIS배열을 하나 생성한다. 이 LIS 배열의 경우 LIS[i]가 나타내는 것은 arr[i]를 마지막으로 가지는 가장 긴 수열의 길이를 의미하게 된다. 즉, 위의 예제입력을 예로 들면 LIS[5]의 경우 arr[5]의 값 즉 50을 가장 마지막으로 가지는 최장 증가 수열의 길이를 의미하게 된다. 이것을 확인하는 원리는 기준의 되는 인덱스 i에 대해 비교 인덱스 j를 두고 1. j

LIS를 이용하여 푸는 문제였다. 예를 들어 1-4 를 연결시켰다고 가정해보면 이제 다음 부터 연결할 수 있는 거는 좌측의 4보다 큰 값을 가진 선만 연결할 수 있게 된다. 따라서 이 문제는 자동적으로 최장 증가 수열의 길이를 찾는 문제가 된다. LIS를 만들 수 있는 방법은 크게 두가지 dp와 lower_bound가 있다. dp의 경우 n^2의 시간복잡도를 가지고, lower_bound는 nlogn의 시간복잡도를 가지는 이문제의 경우 n의 최대값이 40000이기 때문에 dp말고 lower_bound 기법을 적용하여 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

1931.회의실 배정(링크)과 유사한 그리디 유형의 문제였다. 문제를 마주하였을 때 회의실 배정 문제와 상당히 유사하여 비슷한 방식으로 풀게 되었다. 우선 적으로 모든 회의를 시작 시간 기준으로 우선순위 큐에 넣어 정렬을 하였다. 그 후 현재 가장 빠른 시각에 시작된 회의의 끝나는 시간과 그 바로 다음에 시작하는 회의의 시작 시간을 서로 비교하여, 만일 현재회의 끝시간 > 다음회의 시작시간 이면 회의실을 하나씩 추가하는 방식으로 구현해보았다. 회의실 배정과 다른점은 회의실 배정은 하나의 회의실이기때문에 회의들을 1.끝나는 시간으로 회의정렬, 2. 현재 회의의 끝시간, 다음 회의의 시작시간 비교 이러한 방식으로 풀었지만, 이 문제는 회의실 자체를 늘리는 문제이기에 1. 시작 시간으로 회의정렬, 2. 현재 ..

이분탐색을 이용한 문제였다. 집 좌표의 범위가 10억 그리고 최대 값을 구하는 문제여서 이분탐색으로 접근할 수 있었다. 우선 첫번째 집에 공유기를 설치한 것을 가정한 후 이분탐색을 이용해 설치길이를 정하여 다음집에 설치할 수 있는지 없는지 여부를 확인하며 답을 찾아갔다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package algosutdy1; import java.io.BufferedReader; import java.io.InputS..

유니온파인드를 이용하는 문제였다. 문제를 맨처음 접근함에 있어서 파티의 순서가 보장된다고 생각하여 단순하게 생각하였지만, 테스트 케이스를 보고 파티의 순서가 보장되지 않음을 알게 되었고 다시 생각하게 되었다. 다시 생각해보니 같은 파티마다 서로 연결되는 성질을 보았을 떄 유니온파인드가 생각이 나서 적용을 해보았다. 우선 파티의 인원을 전부 입력을 받고, 파티마다 참석자들을 union 해주었다. 그 후 이미 진실을 알고 있는 자 들과 파티의 참석자간의 루트값을 비교하여서 진실을 알고있는 사람들을 모두 선별해주고, 그것을 기준으로 거짓을 얘기할 수 있는 파티를 찾았다. 유니온파인드를 사용할때 주의할점이 있는데 서로의 루트 노드가 같은지를 확인할 때에는 단순히 p[i] , p[j] 값을 비교하는게 아니라 fi..

이 문제는 Trie를 사용하는 문제이다. words라는 배열을 통해 단어들이 주어지고 거기에서 quries에 해당하는 것을 찾는 것을 보고, Trie 알고리즘 이라는 것을 깨닫게 되었다. 다만 이문제에서는 주의할점이 있다. 효율성을 따지기에 일반적인 Trie로는 시간초과가 생기고 만일 문자 '?'를 만나게 된다면 그즉시 단어의 갯수를 리턴해주는 방식을 사용해야했다. 그리하여 Node 클래스에 멤버변수로 count 라는 함수를 만들어주었고, insert과정에서 위치마다 count를 늘려주었다. 또한 '?'가 붙는 방법이 두가지가 있는데 앞쪽에 붙어 단어를 형성하는 fro?? 같은 것이 있고, 뒤쪽에 붙어 단어를 형성하는 ????o 같은 것이 있다. fro?? 같은 경우는 count를 쉽게 리턴해줄 수 있지..

Trie와 백트래킹을 이용한 시뮬레이션 문제이다. 이 문제를 맨처음 보았을 때 일종의 사전 개념인 처음 5개의 입력을 보고 Trie 알고리즘을 사용할 생각을 하였다. 그리고 map이 4x4로써 크지 않고, 주어진 시간도 10초로 충분하여서 백트래킹을 통해 만들어질수 있는 모든 단어에 대해 Trie search를 해주는 방식으로 접근하였다. 여러가지 알고리즘이 혼합되어 있는 형태이기때문에 작은 실수만 해도 어려워 질수 있었던 문제였다. Trie와 다른 알고리즘을 같이 사용해볼 수 있던 좋은 문제였던 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

Trie 알고리즘을 이용한 문자열 문제였다. 이 문제는 노드들이 트리구조로 이루어져있는 Trie알고리즘을 사용한다면 쉽게 풀 수 있었던 문제였다. 입력받을 숫자의 문자열을 정렬을 한후 insert과정에서 말단노드를 만나게 된다면 거짓을 리턴해주는 방식으로 풀었다. Trie 알고리즘은 처음 사용해보았는데 Node 클래스를 만들어서 구현하였다. Node는 멤버변수로 말단 노드를 체크해줄 isEnd와 0부터9까지의 자식노드를 가지게 구현하였다. 그 후 root를 기준점으로 하였고, 문자열의 문자 단위로 자식 노드를 따라가면서 저장할 수 있도록 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..

그리디 하게 접근하여 풀수있는 문제였다. 처음엔 문제를 간단하게 생각하여 내림차순으로 정렬후 두개씩 묶는 방법으로 접근하였는데, 잘 생각해보니 음수에 대해선 오름차순으로 처리하는게 최대값을 출력할 수 있는 것을 알게되었다. 따라서 음수, 양수에 대한 pq를 따로 나누었고, 각 각의 pq에 대해서 2개씩 묶는 방식으로 처리해주었다. 또, 0에 대해서 음수가 홀수개수인경우에 대해서도 예외처리를 해주어야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60..

이문제는 그리디를 이용하여 풀수있다. 문제를 풀기위해 여러가지 방법을 생각해보았다. +와 -에 대해 우선순위를 주는 방법도 생각해보았는데 구현이 생각보다 쉽지 않았다. 결론적으로 이 문제는 -를 기준으로 - 사이에있는 +와 숫자는 모두 연산해줘도 되는 문제였다. 그래서 우선 -를 기준으로 다 나누고, 모든 연산을 해주었다. 그 이후 맨앞에 것을 제외하고 모두음수로 만들어줄수있는 구성을 만들고 모두 더해주어서 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 package study5; import java.io.BufferedReader; i..