코드아키택트 기술편

안녕하세요 집 DS입니다. 지도를 하기로 마음먹었지만 그래도 컴퓨터에 대한 지식은 여전히 필요합니다. 그중 데이터 구조이해로부터 나오는 알고리즘 구현은 특히나 중요한 부분입니다. 모든 부분을 설명할 순 없지만 제가 얘기하고 싶고 이해한 부분을 공유하고자 합니다. 자료구조(Data Structure)란 흔히들 자료구조를 푼다. 자료구조를 구현한다라는 말을 많이 쓰곤합니다. 프로그래밍을 처음 접했을 때나 지금이나 다소 이해가 안 될 때가 있습니다. 그럼 수업 자료를 기준으로 자료구조란 무엇인지 얘기해 보도록 하겠습니다. A data structure is a way to store data, with algorithms that support operations on the data 위 내용을 해석해보면 자..

오늘은 MST(Minimum Spanning Tree) 알고리즘을 neo4j에서 사용하는 법에 대해서 써본다. 굳이 쓰는 이유는 neo4j라이브러리가 업데이트되면서 알고리즘을 쓰는 방법들이 조금씩 달라졌기 때문이다. 그럼 시작해본다. MST? A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. 위키피디아엔 위와같이 정의되어 있다..

문제 https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/ 다음과 같은 Linked List(LL,링크드 리스트)가 주어졌을때, 서로 부딪히는(위 그림의 노란 체크) 노드 찾기 아이디어 일단 같은 길이의 위치에 놓은 후 한칸씩 건너며 체크한다 위와 같은 두 LL이 주어진다고 한다면 긴쪽의 head를 짧은 쪽의 head 에 맞게 옮긴후 이후 한칸씩 움직이면 Intersect 노드를 찾을 수 있음 제약조건 overflow등을 걱정할만한 제약조건은 없어보임 챌린지 time complexity : O(m + n) Space complexity : O(1) 뼈대코드 /** * Definition for singly-l..

https://leetcode.com/problems/merge-sorted-array/ 리트코드의 위의 문제 풀이이며, 아래의 이론을 기반으로 코드를 구성하였습니다. https://www.youtube.com/watch?v=0AIZBg3yFL0&list=PLRJdqdXieSHN0U9AdnmwD-9QcR9hmw04d&index=72&ab_channel=Damn%21ILoveData 문제 코드 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { } } 개념설명 및 문제 위 링크에서 핵심 개념 부분입니다. 필요없으신분들은 스킵하시면 됩니다. 여기서 해결해야할 문제는 nums1안에 nums1 nums2를 정렬해서 넣는것 입니..

Leetcode의 다음 문제에 대한 풀이입니다 https://leetcode.com/problems/search-insert-position/ 문제 정렬된 배열과, 목표값을 가지고 만약 목표값이 배열안에 있으면 그 인덱스를 return하고, 없다면 target값이 들어가기 적합한 위치의 인덱스를 return 예시 Input: nums = [1,3,5,6], target = 5 Output: 2 Input: nums = [1,3,5,6], target = 2 Output: 1 Input: nums = [1,3,5,6], target = 7 Output: 4 Input: nums = [1,3,5,6], target = 0 Output: 0 Input: nums = [1], target = 0 Output: ..

다음 예제는 A*(A-Star) Algorithm 을 사용합니다. 그 전에 A* 알고리즘이 무엇인지 간단한 그림을 통해 이해해보도록 하겠습니다. A* 알고리즘은 무엇이고 어디에 쓰이는가? A*(pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. A*("에이 스타"로 발음됨) 는 그래프 순회와 경로 찾기를 위해 사용되는 알고리즘으로, 그 완결성, 적합성, 그리고 최적 효율 덕분에 컴퓨터 과학 분야에서 종종 사용된다1. 한마디로 경로..

최단거리 찾기(Shortest Path) 하나의 노드쌍에서 최단 거리를 찾습니다. 길찾기 알고리즘은 19세기 부터 유래를 찾을 수 있고, 1956년 Edsger Dijkstra(다익스트라, 데이크스트라)가 가장 유명한 알고리즘을 만들었으며, 대체루트 찾기로 유명해졌습니다. 이 알고리즘을 이해해 보도록 하겠습니다. 위의 움짤을 하나씩 그려가면서 이해해보도록 하겠습니다. 그래프의 구성 그래프의 기본 구성은 다음과 같습니다. 6개의 노드와 8개의 엣지로 이루어져 있습니다. 실생활에 대응해서 생각해본다면 6개의 도시와 이 도시들을 잇는 8개의 도로망이라고 생각해도 됩니다. 그리고 8개의 엣지 위의 값은 거리라고 생각합시다. 최단거리 = 최소 걸리는 루트 라는 공식을 성립하게 하기 위해, 도로체증, 신호 등등의 ..