본문 바로가기
반응형

python61

등수 반환 문제 고찰 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.
변수 메모리 할당 (간단 정리) 메모리 할당 프로그램이 실행되어 메모리에 올라갈때는 해당 프로그램이 사용가능한 메모리 영역을 os로 부터 할당 받는다. 할당 받은 메모리는 크게 4부분으로 나뉜다. 데이터 영역 코드 영역 스택 영역 힙 영역 데이터 영역 상수 값, 정적 변수, 글로벌 변수 등이 할당, 선언된다. 프로그램의 실행과 함께 메모리위에 올라가고, 종료와 함께 메모리에서 해제된다. 그렇기 때문에 정적 변수에 메모리가 큰 값을 할당하는 걸 조심해야 한다. 코드 영역 프로그램의 코드(명령어)가 저장된 공간이다. 해당 명령어를 통해 프로그램의 실행이 제어 된다. 스택 영역 함수 실행시 해당 영역에 필요한 메모리가 할당된다. 함수 내 지역변수, 매개변수, 함수 리턴값 등이 메모리 위에 올라간다. 함수 종료시 해당 영역은 해제되며 재귀 함.. 2023. 7. 31.
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.
LRU cache와 Double-Linked List 그리고 Ordered Dict [leetcode] tl;dr LRU cache 내부 구조는 double-linked list + dictionary(hash table) 형태로 구성 python의 collections.OrderedDict 는 double-linked list + dictionary(hash table) 형태 (삽입된 순서를 보장, 순서를 바꿀 수 있는 내부 함수 제공) 오늘 리트코드로 푼 문제의 제목은 LRU Cache 였다. LRU cache란? 우선, cache가 뭔지 정의되어야겠지? cpu는 연산할 때 사용하는 데이터를 디스크에서 가져오는데, cpu 연산속도에 비해 디스크에서 데이터 조회해 가져오는 속도는 절망적이다. 그래서 중간에 “디스크보다 훨씬 빠르게 조회할 수 있지만 적재는 적게 되는 공간”을 두는데 그게 바로 메모리다. .. 2023. 3. 18.
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.
반응형