본문 바로가기

728x90

스터디/알고리즘

(20)

[hard] 745. Prefix and Suffix Search 문제 https://leetcode.com/problems/prefix-and-suffix-search/description/ 풀이방법 처음에는 단순하게 리스트에서 문자열 비교 방법을 사용했는데, 역시나 시간초과. 두번째로는 아래의 힌트를 참고해서 단어 이어붙인 다음, 문자열 비교하는 방법을 사용했는데 이것도 역시 시간초과. 더보기 힌트 For a word like "test", consider "#test", "t#test", "st#test", "est#test", "test#test". Then if we have a query like prefix = "te", suffix = "t", we can find it by searching for something we've inserted start..

[medium] 583. Delete Operation for Two Strings 문제 https://leetcode.com/problems/delete-operation-for-two-strings/ 풀이방법 word1 에서 몇번의 알파벳 추가/삭제 작업을 거치면 word2를 만들 수 있는지 찾는 문제이다. word1과 word2에서 연속되는 공통부분을 먼저 찾고 공통부분의 길이를 len_subseq 라고 하면, 답은 len(word1)-len_subseq 과 len(word2)-len_subseq 의 합이 된다. 공통부분을 찾는 방법은 현재까지 일치하는 길이를 dp배열에 저장하는 edit distance 방식을 사용한다. word1의 index(wp1)와 word2의 index(wp2) 지점까지의 가능한 가장 긴 공통부분의 길이를 dp[wp2][wp1]라고 할 때, dp[wp2][..

[hard] 51. N-Queens 문제 https://leetcode.com/problems/n-queens/description/ 풀이방법 퀸이 갈 수 있는 방향은 가로(↔), 세로(↕), 대각선(↗,↘) 인데 이때 갈 수 있는 방향에 다른 퀸은 없어야 한다. 이 규칙을 만족하면서 모든 행에 퀸을 배치할 때, 가능한 모든 퍼즐 결과를 출력하면 된다. 각 행, 열, 대각선에는 하나의 퀸만 배치되어야 한다. 그래서 이미 퀸이 배치되어있는 열, 대각선을 각각의 리스트에 저장해놓아야 한다. 열을 저장하는 건 간단한데 대각선은 어떻게 저장해야 하나 싶었는데 아래 표를 보면 row-col 이 동일하면 같은 아랫방향 대각선, row+col 이 동일하면 같은 윗방향 대각선이라는 걸 알 수 있다. 0,0 0,1 0,2 1,0 1,1 1,2 2,0 2,..

[medium] 120. Triangle 문제 https://leetcode.com/problems/triangle/ Triangle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 각 row 마다 하나의 값을 찾아서 이 숫자들의 합이 최소가 되도록 하면 된다. triangle의 각 list가 하나의 row에 있는 숫자들을 저장해둔 것 이므로 각 list에서 하나의 값을 선택해야한다. 이 때, i번째 row에서 선택된 값이 list의 j번째 숫자라면(traingle[i][j]) 그 다음 ro..

이전 1 2 3 다음

728x90

티스토리툴바