본문 바로가기
반응형

알고리즘81

문서 요약 하기 (with textrank) 구글은 pagerank 라는 알고리즘을 통해 검색의 품질을 높혔다. pagerank 알고리즘을 설명해보자면 "더 중요한 페이지는 더 많은 사이트로부터 링크를 받는다" 는 관찰에 기조해 만들어진 알고리즘이다. 위키피디아에 써져있는 예를 보자면 페이지 A가 페이지 B,C,D 로 총 3개의 링크를 걸었다면 B는 A의 페이지 랭크 값의 (1/3) 만큼을 가져온다(?) 풀어서 써보자면 특정 페이지 A 에 B, C, D 의 링크를 걸었다면 ( B 페이지의 중요도(pageRank) + C 페이지의 중요도 + D 페이지의 중요도 ) / 3(=A페이지에 걸린 링크 수) 의 페이지 중요도 (pageRank A)를 가지게 되는 것이다. 또 알고리즘은 인터넷 서핑하는 가상의 인물(random surfer)를 정의 하고, 해당.. 2021. 10. 23.
전력망을 둘로 나누기 [프로그래머스] 문제 넋두리 나는 문제를 set으로 풀려고 했다. 계획은 이랬다. 특정 node(ex.wires[0][0]) 를 left set에 넣는다. wires중 하나를 제거한다. 잘라진(하나가 제거된) wires 배열을 루프돌면서 left set에 wire[0], wire[1]이 존재한다면 left에 추가 한다. 루프가 끝난시점에 left에 담긴 node 와 그렇지 않은 node set 간의 갯수 차이를 리턴 2-4번 (n-1)번 반복 하면서 차이가 제일 작은 값을 answer로 저장 그런데 자꾸 틀렸다. 틀린 이유를 못찾았는데 예상하기로는 left set에 담기는 조건이 wire[0] 이나, wire[1]이 left set에 존재하는지 여부 였는데, (⇒ if wire[0] in left or wire[1] i.. 2021. 10. 9.
예상 대진표 [프로그래머스] 문제 풀이 예전엔 안 풀리던 문제가 이제는 '음~ 너무 쉽고~' 정도로 풀리는 것 같아서 기분이 좋다. 이 문제는 저렇게 말할 정도로 쉬웠기 때문에 설명을 생략할까 하다가 적어본다. (아니 사실은 쉽게 풀어서 기분좋게 글쓴다.) 문제 조건에 써있듯이 부전승이 없다. 게다가 2^n 승의 참가자가 존재한다 = 그럼 무조건 어디선가 만난다. 그림으로 보자. 우리가 주의 깊게 봐야하는건 left와 right를 나누는 저 경계선이다. 저 경계선을 기준으로 left / right 나뉜다면 무조건 n번 경기를 한다. 만약 선수 a,b가 경계보다 작거나, 클경우엔? 경계선을 다시 그려준 뒤, 해당 경계에서 left / right인지 검사, 나뉜다면 n-1번 경기 아니면 다시 경계선 그리기... 이렇게 반복하는 걸 우린.. 2021. 9. 23.
dfs 유형의 문제 [프로그래머스 & leetcode] 프로그래머스에서 풀었던 문제가 마침 leetcode에서 비슷하게 출제되어 푸는김에 같이 정리하는게 나을듯하다. dfs란? 그림으로 보자면, 마지막 노드까지 전부 확인한 뒤, 이동하는 것을 볼 수 있다. 문제를 보자 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 ret.. 2021. 9. 20.
Intersection of Two Arrays II [leetcode] 문제 풀이 설명 어려운 문제는 아니였다. 그래도 역시 생각보다 오래 고민했다. 한 시간 안되게? 일단 교집합이라고 문제 제목이 나와있기 때문에 단순히 교집합으로 풀어야 겠다 생각하면 안된다. 무구한 삽질을 이미 다른 문제를 통해 경험해 봤기 때문에 python이 제공하는 set 연산을 하면 안된다는걸 알고 있다. 첫번째 케이스의 경우 set 연산으로 수행할 경우 [2,2] 가 아니라 [2]로 나오게 된다. → 교집합 연산을 위해서는 리스트가 아니라 집합으로 먼저 바뀌어야 하고 그럼 [1,2,2,1] → [1,2] 로 중복이 제거 나는 이렇게 풀었다 (코드를 보면 알겠지만) 크기가 작은 리스트의 숫자를 꺼낸다. 해당 숫자가 다른 리스트에 들어있는지 판단한다. 들어 있다면 해당 숫자를 크기가 큰쪽에서 제거한.. 2021. 9. 18.
입실 퇴실 [프로그래머스] 프로그래머스 7주차 문제이다. 입실과 퇴실이 반복되는 방에서 어떤 경우에도 반드시 만날 수 밖에 없는 손님을 카운트 하는 문제였다. 어떤 경우에는 만나고, 어떤 경우에는 안만나는 상황은 알고리즘 적인 상황이 아니니 분명 무슨 경우의 수가 있을 것이라 가정하고 풀었다. 공책에 몇번 써가면서 내가 세운 규칙은 입실과 퇴실중 입실먼저 수행한다. 방이 비어있는데 입실과 퇴실이 같다면 아무도 만나지 않고 나간다. 퇴실[0]과 입실[last]가 다르다면 입실 먼저! 퇴실[0]와 입실[last]가 같다면 입실 수행후 퇴실 번호가 없을때까지 퇴실만 수행 입실이 비어있다면 반복을 종료! 로 세우고 문제를 풀었다. 손님들 끼리 만나는 경우 meet_matrix 라는 행렬을 만들어 "O"로 표시, 자기 자신은 만남의 카운트.. 2021. 9. 15.
복서 정렬하기 [프로그래머스] 저번 4주차 때와 마찬가지로 딕셔너리 소팅 문제로 접근해 풀었다. python dictionary sort 정리 (sort by key & value) python dictionary sort 정리 (sort by key & value) 매번 헷갈리고 알고리즘 문제 풀때마다 찾아보길래 이번 기회에 블로그에 적음으로 찾는 수고를 덜고자 한다. 프로그래머스에서 이번에 위클리 챌린지라고 leetcode에서 하는것 처럼 매주 문제 hoonzi-text.tistory.com 각 복서 마다 속성들 몇번 이겼는지 ⇒ win_count 자기보다 무거운 사람과 싸워서 이겼는지 ⇒ weight_count 몇번 선수인지 ⇒ index 자기 몸무게는 몇인지 ⇒ weights[index] 등을 dictionary로 저장하고 해.. 2021. 9. 7.
python dictionary sort 정리 (sort by key & value) 매번 헷갈리고 알고리즘 문제 풀때마다 찾아보길래 이번 기회에 블로그에 적음으로 찾는 수고를 덜고자 한다. 프로그래머스에서 이번에 위클리 챌린지라고 leetcode에서 하는것 처럼 매주 문제 하나씩 내는데 4주차 문제에서 dictionary를 sort해야하는 문제가 나왔다. 3주차는 어려워서 건너뛰고 4주차 풀었다. 내가 생각하는 이 문제의 제일 중요한 부분은 dictionary 자료형의 sort 부분이다. 2번에 대해 자세히 서술해보면 구글에 "python dictionary sort" 를 검색했을때 가장 많이 나오는 답으로는 sort by value 다. value값 크기 대소를 통해 sort 하는 방법이다. # sort by value Ascending result = sorted(dictionary.. 2021. 8. 24.
Reverse Nodes in k-Group [LeetCode] 문제 풀이 정리 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. Example 1: Input.. 2021. 7. 18.
반응형

티스토리툴바