Carat Thinker

깊이 우선 탐색(Depth First Search, DFS) 그래프 완전 탐색 기법으로, 모든 노드를 탐색한다 탐색할 한쪽 분기를 정함 → 최대 깊이까지 탐색 → 다른 분기로 이동 → 반복 아래 사진의 경우, 1 → 2 → 5 → 8을 먼저 탐색하고 2 → 4를 탐색한다. 이후 다른 분기로 이동하여 1 → 3 → 6을 탐색하고 3 → 7을 탐색한다 특징 재귀 함수로 구현한다 스택 자료 구조 이용 : 후입선출 시간복잡도 : O(노드 수 + 엣지 수) 그래프 인접 리스트로 표현 주의할 점 스택오버플로우 : 일정 수준 이상으로 들어가는 것 한 번 방문한 노드를 다시 방문하면 안 된다 : 노드 방문 여부를 체크할 리스트 필요 방문 리스트에 포함되어 있는 노드는 재삽입하지 않는 것이 핵심 단계 인접 리스트로 그래..

그래프란 노드와 에지로 구성된 집합 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결하는 요소 위 그림은 방향이 있는 그래프이다. 그래프는 방향이 없을 수도 있으며, 양방향 그래프일수도 있다. 그래프 표현 방법 에지 리스트 : 에지를 중심으로 그래프를 표현 노드 중심 알고리즘이 아닌 에지 중심 알고리즘에 사용 에지 리스트로 가중치 없는 그래프 표현 방향이 있는 그래프 : 출발 노드와 도착 노드를 표현하는 2개의 열 방향이 없는 그래프 : 2번씩 넣거나(A-B, B-A 순) 1번만 넣고 코딩 시 2번씩 호출한다 에지 리스트로 가중치 있는 그래프 표현 출발 노드, 도착 노드, 가중치를 표현하는 3개의 열 장점 : 구현이 쉽다 단점 : 특정 노드와 관련되어 있는 에지를 탐색하는 것은 어려움 인접 행렬 : ..

정렬에는 병합 정렬 외에도 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 기수 정렬 등이 있지만 시간복잡도가 좋지 않아서 잘 사용되지 않습니다. 오늘은 시간복잡도가 nlogn으로 낮은 편인 병합 정렬에 대해서만 다루겠습니다 병합 정렬 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 분할 정복 방식 분할한 집합을 정렬하며 합친다 2개의 그룹을 병합하는 과정을 이해하는 것이 중요하다 투포인터를 사용한다 과정 데이터를 분할한다 포인터를 세트의 같은 인덱스에 위치시킨다 왼쪽 포인터와 오른쪽 포인터를 비교하여 작은 값을 결과 배열에 추가한다 포인터를 오른쪽으로 1칸 이동시킨다 한쪽 세트의 모든 데이터를 입력했다면 남은 세트의 데이터는 마지막에 배치한다 swap 횟수를 계산하는 응용 문제 등으로..

스택 가장 마지막에 삽입된 data가 가장 먼저 나오는 구조 후입선출 구조 : Last in, First out 삽입과 삭제가 한쪽에서만 일어난다 재귀함수 알고리즘 원리와 일맥상통 삽입 및 삭제 위치 : top 연산 append : 데이터 삽입 pop : 데이터를 삭제하고 삭제되는 데이터 출력 s[-1] : top 위치에 있는 데이터를 단순 확인 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩 테스트에 효과적 백준 10828번 풀이(python) 프로세스 명령 개수 입력 받기 : input 재정의할 것 리스트로 스택 구현 반복문을 통해 명령 입력 받기 입력받은 명령을 명령과 데이터로 분할하기 명령에 따라서 데이터 처리하기 숫자 출력 시 print를 사용하지 않으면 오답으로 처리된다 코드 import sys..

투 포인터 2개의 포인터로 점의 위치를 기록하며 처리하는 알고리즘 과정 시작점과 끝점 = 0번째 인덱스 현재 부분합이 N과 같다면 count +1 현재 부분합이 N보다 작다면 end +1 부분합을 크게 하기 위해서 종료점 이동 현재 부분합이 N보다 크다면 start +1 부분합을 작게 하기 위해서 시작점 이동 2 ~ 4를 반복하며 모든 경우를 확인 백준 1940번 풀이(python) 프로세스 숫자 입력받기 입력받은 숫자를 정렬한다 시작점은 0으로, 끝점은 N-1로 초기화 갑옷의 개수인 count는 0으로 초기화 시작점과 끝점이 같아질 때까지 반복문 수행 시작점과 끝점을 더한 값이 M보다 작다면 시작 위치를 오른쪽으로 이동 시작점과 끝점을 더한 값이 M보다 크다면 끝점 위치를 왼쪽으로 이동 시작점과 끝점을..

배열과 리스트 파이썬에서는 둘을 구분하지 않는다 파이썬의 배열(리스트) 특징 인덱스를 이용하여 바로 접근 가능 가변적인 길이 배열 리스트 인덱스O: 배열의 값에 바로 접근 가능 인덱스X: 접근 속도가 느리다 연속적인 형태 : 삽입, 삭제 속도 느림 포인터로 연결되어 있음 : 삽입, 삭제 속도 빠름 고정된 크기 가변적인 크기 백준 1546번 풀이(python) 프로세스 과목 개수, 시험 성적 입력 받기 최대값 구하기 총합 구하기 : 점수를 일일히 수정하지 않고 총합을 수정해야 시간복잡도를 줄일 수 있다 점수를 일일히 수정하는 방향으로 코드를 짜면 틀린다. 오차 조건때문인듯? 점수 수정하기 : 전체를 최대값으로 나눈 다음, 과목 개수로 나누고 100을 곱한다 코드 n = input() #과목 개수 numbe..

논문 : https://arxiv.org/abs/1511.06939 오역, 오류 등은 댓글로 말씀 부탁드립니다! BackGround 세션 기반 데이터 기존의 추천시스템 : 긴 사용자 기록 대신 짧은 세션 기반 데이터 사용 MF 정확성이 떨어지는 원인 → 현업에서는 아이템 기반 추천으로 MF 정확성 하락 극복 세션 기반 추천시스템 낮은 활용성 데이터 부족 대부분의 이커머스, 뉴스, 미디어 : 사용자별로 행동을 추적하지 않음 → 세션 기반 데이터X 쿠키, 브라우저 지문 데이터는 충분하지 않고 사생활 침해 위험이 있음 트래킹이 가능하더라도 1~2개의 세션만 가지고 있는 경우가 대부분 같은 사용자의 후속 세션은 독립적으로 처리해야 기존 모델 사용자 프로필을 사용하지 않음 과거의 클릭 정보를 무시하고 가장 마지막..

최근에 진행한 공모전에서 특정 좌표와 가장 가까운 지하철역/버스정류장을 계산할 일이 있었습니다. 기준이 되는 좌표가 M개이고, 지하철역/버스 정류장이 N개라면 M X N번의 반복문 루프를 돌려야합니다. 연산 시간을 줄이기 위해 챗GPT를 열심히 돌리고 구글을 뒤진 결과, KDtree를 함께 사용하면 된다는 것을 알았습니다. 데이터 준비 M개의 가게와 가장 가까운 지하철역을 구한다고 가정하겠습니다. 후보가 될 수 있는 지하철은 N라고 가정합니다. 좌표 데이터 확보(위도, 경도) 가게와 지하철역의 좌표가 모두 필요합니다. 지하철역 좌표는 공공데이터셋으로 구축이 되어 있지만, 가게의 좌표를 구하기 위해서는 지오코딩을 실시해야합니다. 지오코딩 과정은 생략하겠습니다. 가게 데이터셋에는 '가까운 지하철역'과 '거리..

최근 팀원들과 함께 전주시 공모전에 나갔었는데요, 저는 네트워크 분석을 담당했습니다. 결과적으로 수상은 하지 못했지만, 텍스트마이닝에 대해서 좀 더 공부할 수 있었습니다. 오늘은 연관규칙 분석과 동시출현빈도를 기준으로 네트워크 분석을 진행하는 법에 대해서 포스팅해보겠습니다. 공모전에서는 두 가지를 모두 사용해봤지만, 시각적인 결과를 고려하여 동시출현빈도만을 보고서에 포함시켰어요. 연관규칙 분석 연관규칙 분석은 주로 매출 데이터를 분석할 때 사용합니다. 어떤 상품이 함께 구매되는지 파악하는 것인데요, 이를 텍스트에 적용한다면 어떤 키워드가 함께 나타나는지를 파악할 수 있습니다. 연관규칙 분석을 위해서는 단어 2차원 리스트가 있어야 합니다. 데이터프레임 내 문장 컬럼을 단어 2차원 리스트로 바꾸기 위해서는 ..

논문 : https://aclanthology.org/P19-1033/ 오역, 오류 등은 댓글로 말씀 부탁드립니다! BackGround 뉴스 추천시스템 개인화된 뉴스 추천시스템 : 방대한 양의 뉴스 중에 관심있는 콘텐츠를 찾고 정보 과부하를 완화하는데 도움 사용자의 선호를 나타내는 정확한 representation을 학습하는 것이 중요 기존 추천시스템 모델 : single representation 학습 single representation : 과거 열람 기록, 추천 기사와 실제 열람한 기사의 유사도 기반 열람 기록 과거의 열람 기록 : 너무 길다 추천 기사와 실제 열람한 기사의 유사도 기반 열람 기록 : latency 발생, 대규모 저장공간 필요 long, short term 선호를 나타내기에는 부족..