Algorithm20 [Medium] 5. Longest Palindromic Substring 길이 [1, 1000] 범위의 문자열 s가 주어지면, 그 안에서 가장 긴 팰린드롬을 찾아 반환하는 문제이다. 팰린드롬이란 "aba", "abba", "eye"처럼 거꾸로 읽어도 동일한 단어를 말한다. 문제 유형은 DP로 분류되어 있었는데, 처음엔 DP로는 어떻게 풀지 방법이 생각이 안나서 그냥 나이브한 방법으로 풀었고, 두 번째에는 디스커션을 확인하여 DP로 풀었다. 1) 우선 내가 푼 방법이다. 나는 s의 첫 문자부터 시작해서 끝까지 순회를 할 것이다. 현재 문자가 s[i]라면 맨 뒤에서부터 s[i]와 동일한 문자를 찾는다. 찾은 위치의 인덱스가 j라고 했을 때, [i, j] 범위를 검사하여 팰린드롬인지 확인한다. s[j]는 가장 뒤에서부터 찾은 문자이므로 s[i]에 대해선 가장 긴 팰린드롬이 된다. .. 2021. 9. 27. [Easy] 338. Counting Bits int타입 n이 주어지면 n+1 길이의 int형 배열을 생성하고 이 배열의 i번 째 원소를 i를 이진수로 나타내었을 때 1의 개수로 채워서 반환하는 문제이다. 즉 3번째 원소는 3(0011)의 1의 개수인 2이다. 처음엔 그냥 쉽게 bitset 클래스를 이용하여 풀었는데, 분류가 DP로 되어 있어서 DP 풀이법을 봤더니 내 머리로는 생각도 못했을 방법이었다. 우선 bottom-up 방식으로 낮은 원소부터 채운다. 그리고 i번째 값은 두 부분으로 나누어서 구한다. 한 부분은 첫 번째 비트 부분이고 한 부분은 나머지 비트 부분이다. 예를 들어 i가 3일 경우, 3을 2로 나눈다. 2로 나누는 것은 1bit만큼 right shift 하는 것과 같다. 그러면 0011이 0001이 되고 이는 십진수로 1이다. 그.. 2021. 9. 26. [Easy] 121. Best Time to Buy and Sell Stock 각 [i] day의 주식 가격이 담긴 int형 배열이 주어지고, 주식을 사고 팔아야 할 때 수익을 최대화하면 수익이 얼마인지 구하는 문제이다. 예를 들어 첫 번째 예에서 가격이 1일 때 사서 6일 때 팔면 수익이 5로 최대가 된다. 처음엔 배열 profit을 선언하고 profit[i]를 i에서 살 때 최대 수익으로 정의했었다. 그러면 price[i]를 기준으로 그 뒤에 가격들에 대하여 한 번씩 확인하였다. 즉 이중 루프가 되는데 시간 초과가 떴다. 아직 알고리즘 문제를 많이 접해보지 않아서 그런지 방법이 바로 생각나지 않았다. 생각을 좀 해보다가 profit[i]를 i에서 살 때가 아닌 팔 때의 최대 수익으로 정의하였더니 쉽게 풀렸다. 우선 profit[0]은 항상 0이 된다. 그리고 i 이전의 min .. 2021. 9. 26. [연습문제] 최고의 집합 int 타입의 n과 s가 주어지는데, n개의 수로 집합을 구성하여 모든 원소의 합이 s이고 모든 원소의 곱이 가장 큰 집합을 찾아내는 문제이다. 찾을 수 없다면 -1을 반환한다. n개의 수를 모두 사용해야 하기 때문에 찾을 수 없는 경우는 n이 s보다 큰 경우를 말한다. 각 원소는 자연수이여야 하기 때문에 s가 3이고 n이 5면 제일 작은 수 1로 구성하더라도 3을 넘기 때문에 불가능하다. 그리고 3, 3처럼 s와 n이 같다면 가장 작은 수 1로 구성해야 하므로 1을 n개만큼 만들어 반환하면 된다. 만약 s가 n으로 나누어 떨어진다면 n개의 수를 s/n으로 구성하면 된다. 그밖의 경우 s가 n으로 나누어 떨어지지 않는다면, 우선 s를 n으로 나눈다. 만약 예제의 9를 2로 나눈다면 몫은 4가 되고 나머지.. 2021. 9. 24. [Level 3] 섬 연결하기 각 노드를 최소 비용으로 연결시키는 문제이다. 최소 신장 트리를 만드는 Kruskal 알고리즘을 사용하면 된다. 알고리즘은 간단하다. 우선 cost를 기준으로 오름차순 정렬시킨다. i번 째 cost를 골라 두 섬이 연결되어 있는지 확인한다. 만약 연결되어 있다면(같은 그룹이라면) 다시 연결할 필요없다. 만약 연결되어 있지 않다면 (같은 그룹이 아니라면) 두 노드를 연결시키고(같은 그룹으로 표시) 해당 비용을 누적시킨다. 이를 모든 costs 요소에 대해 확인하면 된다. 여기서 핵심은 두 섬이 서로 연결되어 있는지, 같은 그룹에 있는지 확인하는 방법이다. 방법은 생각보다 간단한다. 우선 섬의 개수인 n의 크기를 가지는 int 타입 원소를 저장하는 1차원 배열을 하나 생성한다. 초기값은 모두 -1로 설정한다.. 2021. 9. 21. [Level 3] 단속 카메라 겹치지 않는 범위는 어쩔 수 없이 카메라를 1대 주고, 겹치는 영역은 최대한 겹치도록 하면 된다. 비교를 위해 먼저 시작 지점을 기준으로 오름차순 정렬한다. 그다음 반복하면서 [i]와 [i+1]의 범위를 비교하여 [i+1]의 시작 지점이 [i]의 종료 지점보다 크면 겹치지 않는 것이므로 어쩔 수 없이 카메라 1대를 주고 넘어간다. 만약 [i+1]의 시작 지점이 [i]의 종료 지점보다 작거나 같다면 1칸이라도 겹치는 것이므로 새로운 영역의 시작 지점을 [i+1]의 시작 지점으로 업데이트한다. 종료 지점은 더 작은 지점으로 업데이트한다. 다음엔 이 새로운 영역과 비교해서 겹친다면 영역을 또 업데이트하던지, 겹치지 않는다면 현재까지의 영역에 카메라를 한 대주고, 다시 반복하면 된다. #include #incl.. 2021. 9. 21. 이전 1 2 3 4 다음
