본문 바로가기
반응형

파이썬93

등수 반환 문제 고찰 Q. 성적이 입력되고 그 학생의 등수를 출력하는 함수를 작성하시오. 점수는 0~100이고, 점수는 랜덤으로 들어온다. rank 함수는 20억 회 이하로 동작된다.(대충 이런 내용) 전역변수, 클래스 등 자율적으로 사용해도 무관. 시간과 메모리 등을 고려하여 작성 ex. 1번째: Score: 70 -> return 1 2번째: Score: 100 -> return 1 3번째: Score: 80 -> return 2 4번째: Score: 70 -> return 4 5번째: Score: 50 -> return 5 문제 출처 : https://okky.kr/articles/1052166 문제 해결을 위한 rank 계산 코드 짜기 version 1. 첫번째 접근 → 단순히 리스트에 넣고, 정렬하고, 해당 숫자 찾.. 2023. 10. 20.
number dictionary 선언시… 나는 여태껏 python dictionary를 사용할 때, key값이 어떤 값이던간에 key:value 형태로 사용하곤 했다. key 값이 숫자건 문자건 key가 생성되어 있다면 value를 추가(혹은 수정) key가 없다면 key에 대해 정의한뒤 value를 추가 하는 식으로 말이다. (defaultDict 안쓰는 고집이 있다.) 가령 예를 들어, 무방향 그래프에서 각 노드 간 연결이 아래와 같이 주어진다고 할 때 connections = [[0,1],[0,2],[1,2]] 이걸 dictionary 형태로 구성한다면 connections = [[0,1],[0,2],[1,2]] num_dict = {} for conn in connections: a,b = conn[0], conn[1] if a not .. 2023. 3. 26.
binarySearch를 정렬된 리스트에 insert를 위해서만 사용한 나 조금 무례할지도 [leetcode] 알고리즘 문제를 풀다 보면 정렬된 배열에서 특정 숫자가 들어갈 자리 찾는 문제를 자주 만나게 된다. 그런 문제들 만날 때마다 ‘아 또 binary search 쓰라는 말이구나’ 하고 기계적으로 코드를 치는데 오늘 만난 문제는 좀 달랐다. 풀이도 신박했어서 그거에 대해서 써보려고 한다. 그냥 배열 순회하면서 하나씩 비교하면 금방 찾겠네~ 아 껌이네~ 근데 medium?? 특이한 요구사항이 하나가 있다. Your solution must run in O(log n) time and O(1) space. 문제가 단순해 보여서 그런지 머릿속으로는 ‘그냥 순회하면서 하나씩 비교하면 바로 나오지 않나?’ 밖에 생각나지 않았다. 그렇지만 그럼 O(n) 이기 때문에… class Solution: def singleNo.. 2023. 2. 22.
심심해서 해본 글자 돌리기 저번에 친구랑 얘기하다 나온 요즘 핫한 사건 https://news.mt.co.kr/mtview.php?no=2023021023543967230 죽은 아내가 낳은 불륜남 아기…"출생신고라도" 남편 설득하는 市 - 머니투데이 숨진 아내와 다른 남자 사이에서 태어난 아이를 산부인과에 남겨둔 법적 친부에게 청주시가 "출생신고라도 하라"고 설득하고 있는 것으로 전해졌다. 10... news.mt.co.kr 여기 등장하는 “친생자관계부존재확인”라는 단어가 있다. 중요한 건 단어의 의미가 아니고 마침 열 글자였다는 데 있다. 마침 심심했던 찰나에 이걸보고 쓸데없는 호기심이 발동… 4 글자씩 끊어서 쳐보니 아래와 같이 나온다. 그렇게 친 글자를 세로로 연결해 새로운 글자로 만들면 전혀 다른 글자가 나오고… 그럼 이걸.. 2023. 2. 20.
python 으로 구현하는 간단간단 검색엔진 로직 inverted index를 알아보다 검색엔진 기본 로직을 작성해보는 글~ 목표 역색인과 검색엔진로직에 대해 간략히 알아보고, 해당 부분을 코드로 구현해 보자. 기존 관계형 데이터베이스에서는 텍스트 검색 시 걍 full-scan으로 검색해 결과를 반환한다. 물론 full-text search를 지원하지만 (https://dev.mysql.com/doc/refman/5.6/en/innodb-fulltext-index.html#innodb-fulltext-index-design) 비정형 데이터인 텍스트 검색을 위해 만들어진 엘라스틱 서치보다 나을까? 엘라스틱 서치의 강점으로는 아래와 같다. 전문 검색 엘라스틱서치는 전문 검색(Full Text)이 가능하다. 전문 검색이란 내용 전체를 색인해서 특정 단어가 포.. 2022. 12. 30.
편집거리 알고리즘을 통한 검색어 자동완성 보정 (ft . Levenshtein Distance) 저번 검색어 자동완성 글 말미에 오타가 들어가 있는 경우, 제대로 된 단어로 유추될 수 있으면 좋겠다는 생각을 했는데 마침 적당한 알고리즘이 있어서 실제로 실습해봤다. 브랜드 이름 검색어 자동완성 2 (with Suffix Trie) 저번 Trie를 이용한 검색 자동완성의 연장선의 글이다. 브랜드 이름 검색어 자동완성 with Trie 브랜드 이름 검색어 자동완성 with Trie 인터넷을 돌아다니다 글을 하나 보게 됐다. 카테고리 자동완성 hoonzi-text.tistory.com 레벤 슈타인 알고리즘이라고… 이름부터 어렵지만 막상 까 보면 생각보다 별거 없는 알고리즘이 있다. 두 문자열이 얼마나 다른지 값으로 나타내주는 알고리즘으로 문자를 삽입, 삭제, 치환하여 다른 문자열로 변형하는데 필요한 최소 .. 2022. 11. 26.
브랜드 이름 검색어 자동완성 2 (with Suffix Trie) 저번 Trie를 이용한 검색 자동완성의 연장선의 글이다. 브랜드 이름 검색어 자동완성 with Trie 브랜드 이름 검색어 자동완성 with Trie 인터넷을 돌아다니다 글을 하나 보게 됐다. 카테고리 자동완성 개발기 카테고리 자동완성 개발기 안녕하세요. 29CM 발견스쿼드에서 백엔드개발을 담당하고 있는 이동권입니다. 검색페이지에서 hoonzi-text.tistory.com 저번 검색어 자동완성의 경우, 검색어를 앞글자부터 Trie로 구성하기 때문에 중간에 나온 단어의 경우 검색어 자동완성에 노출되지 않는 문제가 있다. (예를 들어 “디”라는 단어를 칠 때 “디올” 은 나올 수 있지만 “아디다스”는 나오지 않는 문제가 있다.) suffix Trie는 이 문제를 해결하기 위한 자료구조로 기존 Trie(pr.. 2022. 11. 19.
브랜드 이름 검색어 자동완성 with Trie 인터넷을 돌아다니다 글을 하나 보게 됐다. 카테고리 자동완성 개발기 카테고리 자동완성 개발기 안녕하세요. 29CM 발견스쿼드에서 백엔드개발을 담당하고 있는 이동권입니다. 검색페이지에서 카테고리 자동완성 기능을 개발한 경험을 공유합니다. medium.com 어느 쇼핑몰의 검색어 자동완성에 대한 글을 봤다. 간단히 요약하자면, Trie 자료구조를 이용해 단어를 저장하고, 검색 시 조건에 맞는 단어를 보여 준다는 글이다. 다 읽고, ‘오 이정도면 한번 구현해볼 만 한데?’ 싶어서 작업에 들어갔다. 대략 순서는 이렇다. 데이터 수집 Trie 자료구조에 저장 결과를 반환해줄 api , html 페이지 구성 글을 읽은 것과 코딩을 시작한건 시간차가 좀 있다. 그래서 그런지 저 기술 블로그가 ‘무신사’라고 착각해 데.. 2022. 11. 7.
circular-queue 자료구조와 문제풀이 [leetcode] 진짜 백만 년에 알고리즘 문제풀이에 대해서 글을 쓴다. 그동안 잘 안 썼는데, 문제 푸는 것보다 글 쓰는 게 더 어렵다고 느껴졌기 때문이다. 그렇지만 이번에 쓰는 이유는 내가 잘 안 쓰는 자료구조이기도 하고, 학교 다닐땐 알고리즘 코딩 테스트에서 못 풀었었는데 지금은 푼 기념으로 정리하고자 글을 적는다. 이번에 쓸 자료구조는 queue의 변형인 circular-queue 다. 우선 queue 란, stack 자료구조와 다르게 first-in first-out (FIFO)의 입출 로직을 갖는 자료구조를 얘기한다. 여기에 빈 배열이 있다고 치자. [ ] 차례로 1,2,3 의 숫자를 집어넣는다 치면 (enqueue라고 한다.) [1,2,3]으로 들어가고, 꺼낼 땐 (dequeue라고 한다.) 1 ← [2, 3.. 2022. 9. 28.
반응형