본문 바로가기
반응형

분류 전체보기153

다문서 요약 하기 (multi-document summarization) 요즘 요약에 관심이 있어서 관련 논문을 찾아 보던중 (취미로) ‘아 이건 나도 구현이 가능할 것 같은데?’ 싶은 논문이 있어서 정리해보려고 한다. 문서 하나에 대해 요약하는 건 블로그에 정리한게 있다. (물론 생성요약이 아니라 추출요약이다.) 요약은 크게 추출 요약 (extractive) 과 생성 요약 (abstractive) 으로 나뉜다. 오늘 해볼 건 추출요약 (extractive) 이다. 참고한 논문은 Clustering Sentences with Density Peaks for Multi-document Summarization 으로 비슷하게 주제의 기사들의 ‘문장’ 들 간의 밀집도를 바탕으로 중요한 문장을 ‘추출’ 한다. 이 논문에서는 중요도를 크게 3가지로 나누었는데, representativ.. 2022. 3. 1.
Remove K Digits [leetcode] 문제링크 문제 풀이 Input: num = "1432219", k = 3 Output: "1219" 첫번째 풀이 처음에는 앞 숫자와 뒤 숫자를 비교해서 뒤 숫자가 크면 해당 숫자를 지우는 로직인줄 알았다. 그럼 위 예시로 보면 1 : “4” 32219→ 4가 크므로 4를 지운다 ⇒ 132219 (k =2) 1 : “3” 2219→ 3이 크므로 3을 지운다 ⇒ 12219 (k=1) 1 : “2” 219→ 2가 크므로 2를 지운다 ⇒ 1219 (k=0 이므로 종료) 그럼 정답으로 1219 이므로 쉽게 푼줄 알았다. 하지만 반례로 Input: num = "12345", k = 2 Output: "123" 위 반례가 있다. 1 : 2 → 2가 크므로 2를 지운다 ⇒ 1345 (k=1) 1 : 3 → 3이 크므로.. 2022. 2. 19.
Swap Nodes in Pairs [leetcode] 문제 문제 풀이 정리 의외로 머리속에서 정리가 안되던 문제였다. 그림을 보면 알겠지만 짝수 일때만 자리를 바꿔줘야 한다. 하지만 List(배열) 이 아니고 Linked List 이기 때문에 인덱스로 접근할 수 없다. 그래서 even_flag를 만들어서 마치 짝수일때만 동작할 수 있도록 한다. 현재 위치가 짝수일 때와 홀수일 때 로직이 다른데 적어보자. 홀수일 때 현재 노드는 이전 노드로 지정한다. (prev = curr) 현재 위치를 다음 노드로 옮긴다.(혹은 지정한다.) (curr = curr.next) 짝수 플래그를 true로 변경한다. if even_flag == False: prev = curr curr = curr.next even_flag = True 짝수일 때 이전 노드의 next를 현재 노.. 2022. 2. 16.
쿼드압축 후 개수 세기 [프로그래머스] 문제링크 문제풀이 예전에 한번 문제만 봤던건데 예전과 달라진 점은 이제 그림을 보고 “오! 재귀함수로 풀면 금방 풀리겠다” 가 보이는 단계로 진화했다. 문제풀이 각이 보이니 얼른 풀었다. 입력으로 들어오는 arr 행렬을 4등분해서 갯수를 세면 되겠다 싶었다. 규칙으로는 arr 행렬 4등분 하기 arr 의 길이가 1 이라면 해당 배열의 숫자 그냥 반환하기 4등분 된 각 부분의 모든 숫자가 같다면 그 숫자 하나만 반환하기 (압축) 그렇게 제일 작은 부분부터 사분면 합치면서 재귀함수 빠져나오기 하나씩 구현해보자 arr 행렬 4등분하기 def slice_arr(arr, upDown, direction): temp_arr = [] slice_num = len(arr)//2 if upDown == "up": # 가.. 2022. 2. 14.
Subsets [leetcode] 문제 Subsets - 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 문제풀이 문제 예시로 나온 답을 보고 풀게 되었다. Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 규칙이 보이는가? output 에 처음에는 [] (빈 리스트) 공집합 하나만 추가해준다. num = 1 일때, output 을 순회하면서 이전 집합에 1을 추가한다. (temp_list = [] + 1 = [1]).. 2022. 2. 13.
Permutation in String [leetcode] 문제 문제 풀이 문자열의 퍼뮤테이션 이 존재하는지 여부 판단 문제이다. 문자열의 퍼뮤테이션은 문자열의 길이가 길어질수록 연산량이 급격히 증가하기 때문에 다른 식으로 풀었는데 바로 dictionary (다른말로 Map) 이다. 순서만 바뀐 문자열의 경우, 사용된 문자와 해당 문자 개수가 같다는 점을 이용해 { “a” : n개, “b” : m개, ...} 등으로 나타내 같은 키 값을 가지고 있는지, 서로 다른 키가 존재하지 않는지 여부 같은 키 값에 대해 동일한 수량을 가지고 있는지 여부 를 검사하면 퍼뮤테이션 연산을 피할 수 있다. 코드상으로는 dictionary를 만드는 함수 dictionary 2개를 서로 비교하는 함수 를 구성했다. #dictionary를 만드는 함수 def dictCreate(sel.. 2022. 2. 11.
K-diff Pairs in an Array [leetcode] 문제 풀이 리스트 안 숫자들 중 차이의 절대값이 k를 만족하는 숫자 쌍 의 개수를 찾는 문제다. 한국말로 한문장 정리하니 “의” 로 연결된게 많아 국어지문 푸는것 같다. 다시 정리하자. 리스트 안 숫자들 중 ⇒ ex. [3,1,4,1,5] 차이의 절대 값 ⇒ ex. |3 - 1| = 2 k를 만족하는 숫자 쌍 count! ⇒ ex. |3-1| == 2 ? (count +1) : nothing! 문제를 보면 리스트의 중복된 숫자가 있어도 1개로 친다고 한다. 그럼 로직상 중복체크도 필요하다는 얘기다. 나는 이렇게 풀었다. 현재 비교할 숫자 = nums[i] 비교 당해야 할 숫자들 = nums[i+1:] (중복을 피하기 위해 i 번째 이후 숫자들만 사용) 중복을 피하기 위해 num_set 생성 ⇒ num_s.. 2022. 2. 9.
Find All Anagrams in a String [leetcode] 문제 https://leetcode.com/problems/find-all-anagrams-in-a-string/ Find All Anagrams in a String - 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 문제 풀이 설명 긴 문자열 (이하 s) 에서 짧은 문자열(이하 p)의 anagram(알파벳 순서를 바꾼 문자열) 을 찾는 문제이다. 해당 문자열이 s에서 발견될 경우, 발견된 위치를 전부 리턴하면 되는 문제이다. anagram은 문자의 순서를 바꿔.. 2022. 2. 2.
배달 [프로그래머스] 문제 풀이 설명 그래프 보자마자 음 이건 dfs 문제군 이라고 감이 왔다. 확실히 예전보다는 문제를 많이 풀어봐서 감을 익힌듯 하다. 그래프 그림을 보면 주의 할 점이 보이는데, cycle 이 존재한다는 점이다. 연결된 node를 따라갈때, recursive 하게 함수를 짜게 되는데, 끝이 없다면 stack overflow로 에러가 날수 있다. 그래서 visited 라는 배열을 만들어 이전에 방문한 node에 대해 체크할 수 있도록 구현했다. 우선 road 매트릭스를 만들어 준다. 매트릭스 mat[i][j] 는 i번째 마을과 j 번째 마을의 road 길이로 세팅해준다. 각 마을 별로 방문했는지 여부를 알 수 있게 visited 리스트 역시 만들어준다. mat = [] for i in range(N): #.. 2022. 1. 29.
반응형

티스토리툴바