자료구조 & 코딩 테스트 문제 해결 패턴

Problem size 의 배열이 있을 때, 해당 배열로부터는 크기 의 연속된 배열을 개 만들 수 있다. 만들 수 있는 배열 중에서 가장 큰 합은 무엇인가? solution slower, but pythonic way 사실 아래 방법이 보통 파이...

Problem 문자열 s 로부터 만들 수 있는 가장 짧은 Palindrome을 만들어주는 함수입니다. s가 이미 Palindrome라면, 해당 문자열을 그대로 리턴하면 되고, 아닐 경우에는 해당 문자열을 이용해 새로 만들어줘야겠죠. solutio...

Problem n n matrix를 입력받아, 해당 매트릭스에서 스도쿠의 요건이 성립하는지를 체크하는 함수 - 모든 row에 1 - 9 까지의 모든 값이 있을 것 - 모든 column에 1 - 9 까지의 모든 값이 있을 것 - 3칸 씩 잘라서 만...

Problem 특정한 수 가 들어왔을 때, 의 인수 들을 조합해 만들 수 있는 가장 작은 수를 찾는 함수입니다. 이 문제는 약간 이해가 어려울 수 있어서, 예를 중심으로 설명합니다. examples 1. digitsProduct(2) ==> 2 ...

Problem 은 나선형 이라는 뜻인데, 달팽이집처럼 뺑뺑 돌아나가는 것을 의미하고 spiralNumbers(n)은 음...예시를 보는 게 더 빠를 것 같다. examples 1부터 입력받은 정수까지를 nn matrix에 시계방향으로 배치하고 해...

Problem tree 가 주어졌을 때, leaf로부터 root까지의 합이 s인 path가 존재하는지를 찾는 함수를 만듭니다. example Define Tree(binary) linked list 말고도 Tree 형태의 자료구조도 있습니다. 여...

Problem linked list 이 Palindrome인가? 를 확인하는 함수 ReversedLinkedList(head) Palindrome인지를 확인하기 위해서는 Reverse하는 것이 중요하고, 이를 따로 함수로 정의하였습니다. - 간단...

Problem 두 non-increasing linked list가 들어왔을 때, 이 둘을 합친 non-increasing linked list를 만드는 함수 example mergeTwoLinkedList([0, 1, 5], [3,3,3,7])...

Problem linked list 에 가 포함되어 있을 경우, 모든 를 삭제하고 삭제된 linked list를 리턴하는 함수를 만듭니다. example removeKFromList([3,1,2,3], 3) ==> [1,2] solution

Problem linked list를 k 개만큼씩 끊고 각자 reversing하여 다시 연결해주는 함수를 말한다. example reverseNodesInKGroups([1,2,3,4], 2) ==> [2,1,4,3] reverseNodesInK...

Problem 매트릭스를 회전하는 함수를 만들어 봅니다. - Transpose 는 diagonal line을 축으로 회전해주는 것이고, 여기서 만들려고 하는 것은 matrix의 중심에서 회전시키는 것을 말합니다. - 역시 예제로 설명하는 것이 좋...

intro dynamic programming은 음...일단은 'recursion'이라고 생각해도 상관없다. 이전에 계산한 값을 가지고, 이후의 값을 계산할 수 있는 것을 의미하는데, 쉽게는 fibonacci가 이 경우에 포함된다. - knaps...

Problem 간단한 코드로 쓰자면 다음과같다. 다만, 현재는 계산속도가 느려서 개선하고 있는 상황. - nums: int list - ex: [1,2,3,4,5,6] - queries: list of (position pair) - ex: [[...

Problem n 4 의 직사각형을 2 1 혹은 1 2의 직사각형으로 채워야 할때, 채울 수 있는 방법의 수는 총 몇 가지 인지를 리턴하는 함수입니다. - if n==1: 1 4 인 직사각형은 2 1을 가로로 두 번 채우는 것 밖에 방법이 없음 ...

Problem https://codefights.com/interview-practice/task/mkobsYSSQo3JpvYNN/ 0, 1로 구성된 2 dimensional binary matrix(직사각형) 내부에 있는 가장 큰 정사각형의 넓...

Problem 순서대로 배치된 집을 색칠하려고 한다. - 방법은 총 3가지 - 집마다 색칠할 때의 가격은 다르며, i 번째 집을 j 색으로 칠할 때의 가격은 - 연속된 집은 같은 색으로 칠하면 안된다. 모든 집을 칠할 수 있는 가장 적은 가격을 ...

Problem https://codefights.com/interview-practice/task/Sx8ndFtwEyCRRqF7q/ string s가 regular expression 으로 정의된 pattern p를 따르는지를 체크하는 함수를 만...

Problem 는 2 dimensional array로, 가 1이면, node 가 연결되어 있음을 의미한다(o/w 0) connections를 이용하여 네트워크를 그릴 수 있으며, 입력받은 connections의 경우 모든 노드가 연결되어 있다....

Problem binary tree t가 symmetric한지를 검사하는 함수입니다. define binary tree value, left, right를 가지는 아주 간단한 객체. shallow copy를 조심하기 위해서, copy functi...

Problem palindrome이 무엇인지는 이미 다들 알고 계신것 같아용, 앞뒤로 읽어도 똑같은 스트링을 말합니당(1577 1577말고 1577 7751 이용) 다만, kpalindrome의 경우는 해당 문자열에서 k개 이하의 문자를 삭제했을...

Problem Given , find the longest IncreasingSubsequence. - 정확히는 길이만 계산해주면 되는 함수 example consecutive가 아니고, integer position 상에서 앞과 뒤의 관계만 지...

Problem string 를 입력받고, 존재하는 파일 중 string size가 가장 긴 path 를 찾아서 리턴해주는 함수를 만든다. 를 프린트하면 다음과 같다. - picture와 documents의 경우, user의 하위폴더이며, phot...

random tree 만들기 random tree를 만들거에요. tree라는 것은 parent, children를 가지는 스트럭쳐죠. 저는 parent, children로 node를 접근하는 건 만들지 않았습니다만, random 하게 tree를 ...

tree에 적합한 layout을 찾습니다. networkx에는 다양한 layout이 있습니다만, tree 구조에 적합한 레이아웃은 없어요(정확히는 없다고 생각했습니다). 그런데 사실 없다는게, 제 입장에서는 말이 안되서 한참 찾았는데, 찾다보니 ...

random하게 tree를 만듭니다. 예전에 제가 직접 random하게 tree를 만들어주는 코드를 만들었습니다. random하게 각 level별 node의 수를 정하고 children의 수도 랜덤하게 정해서 진행했는데, 생각보다 만드는데 시간이...

tree에서 Root 찾기 networkx의 를 사용해서 tree를 만들고 관리하는데, 그때 적절한 root를 찾는 것이 중요해요. 또 해당 root를 중심으로 다른 node들이 얼마나 멀리 떨어져 있는지를 파악하는 것도 중요하구요. 그래서 아래...

intro 이번 주는 집에서 휴가를 보내고 있습니다. 어쩌다 이런 인간이 되어버렸는지는 잘 모르겠지만, 저는 휴가에도 제가 평소에 관심이 있던 공부를 합니다. 아주 좋은 습관이라고 생각하고 있기는 한데 또 어쩌다 이런 인간이 되어버렸는지, 약간 ...

intro 최근에 최적의 tree구조를 찾아내는 연구를 수행하고 있습니다. 그 과정에서 처음에는 genetic algorithm을 활용하여 최적화로 풀어보려고 했는데, 이 방법 외에도 강화학습을 쓸 수 있지 않을까? 라고 막연하게 생각이 되었어요...

intro monte-carlo tree search를 공부해보던 중에 tree구조를 사용해볼 필요성이 생겼습니다. 물론 를 이용해서도 비슷하게 만들 수 있지만, 이때는 find parent, find children 등에서 약간 불편함이 발생하...

요즘 심심할때 간단한 코딩 문제를 푸는데, 간단한 자료구조가 나옵니다. 이른바 heap이라는 것이죠. complete binary graph(대충, children이 두개 씩만 있어야 하고, 음, 대충 꽉 채워진 그래프입니다 설명하기 귀찮네효 하...

네트워크의 기본적인 장비들 네트워크에서 사용되는 기본적인 장비들의 개념들을 정리했습니다. 허브 - L1 Physical Layer 우선, 기본적으로 '허브'와 '스위치'는 모두 네트워크 멀티탭이라고 생각하면 됩니다. 사실 이게 되게 직관적인 설명...

LAN(Local Area Network) 우선, LAN은 "근거리 통신망"을 말합니다. 집, 사무실 게임방 처럼 하나의 구역 내에 연결된 근거리통신망을 말하죠. LAN보다 작은 것은 PAN(Personal Area Network), 즉 개인통신...

왜 Dynamic Array가 필요한가? 일반적으로 Array를 사용할 때는 다음처럼 메모리의 크기를 처음에 잡아놓고 시작합니다. 다음의 코드에서는 3개의 크기의 메모리를 잡은 것이죠. 그 메모리에 우리는 3개의 int형 정수를 배치하여 사용할 ...

List 내 Inversion 개수 찾기 Array 혹은 List가 있을 때, 현재의 상태를 Sorted와 비교하여 얼마나 차이가 있는지 확인하려면, 현재 순서가 반대로 되어 있는 pair들이 얼마나 있는지 확인하면 되겠죠. 이렇게 역순으로 되어...

이상한 짓을 합니다. - 비어 있는 list 를 만들고요. - reference variable 가 를 지칭하도록 합니다. - 그리고 안에 를 넣어줍니다. 좀 이상하지 않나 싶지만, 오류 없이 잘 돌아갑니다. 그냥 print해서 안에 있는 값을 ...

Install Cisco Packet Tracer Cisco Packet Tracer for MAC을 다운받아 봅시다. 다운받아서 Next를 연타하여 설치합니다. 그리고 나면 "Cisco Packet Tracer", "Linguist", "mai...

python에서 dictionary는 매우 유용한 자료구조이기는 한데, 가 dictionary에 존재하지 않는 경우를 고려해야 해서 꽤 귀찮죠. 가령, 에 있는 원소들의 빈도를 센다고 하면 다음과 같이 코딩해야 합니다. 별것 아닌데 꽤 귀찮죠. ...

java를 사용해서 tree를 만들어봤습니다. childNode의 개수에는 제한이 없고, 다음 method를 구현하였습니다. - : 자식 Node를 집어넣는다. - : Node가 존재하는지 찾는다. - : tree의 길이를 계산한다. - : tr...

Java로 3명의 child를 가지는 Tree를 구현했습니다.

Java에서 Binary Search Tree를 구현했습니다. 가 꽤나 어려웠는데, 지워야 하는 node의 자식 노드가 2개인지 1개인지(왼쪽인지, 오른쪽인지) 없는지에 따라서 과정이 조금씩 달라집니다. 뿐만 아니라, 이 때, 지운 다음 pare...

Java로 Binary Heap을 구현했습니다. Binary Heap은 다음 조건을 만족하는 자료 구조를 말하죠. Heap은 작을수록 우선순위를 가지는 MinHeap과, 클수록 우선순위를 가지는 MaxHeap으로 나뉘는데, 여기서는 MinHeap...

CountingSort는 현재 array 내에 존재하는 원소의 빈도를 활용하여 sorting하는 방식을 말합니다. '빈도'를 고려하는 것처럼, 원소들이 중복되어 있을 수록 효율적이죠. 보통의 알고리즘들은 모든 원소들간의 값을 비교하여 정렬하는 반...

binary search tree를 구현해봤습니다.

간단하게 merge sort를 구현해 봤습니다. quick sort는 pivot을 기준으로 작으면 다 왼쪽, 크면 다 오른쪽으로 두면서 정렳하는 방식이라면, merge sort의 경우는 왼쪽 애들은 왼쪽대로 정렬하고, 오른쪽 애들은 오른쪽 애들대...

Sorting 알고리즘 개발시에는 무엇을 주로 고려해야 하는가? Time Efficiency: 얼마나 빠른 시간 내에 정렬을 수행할 수 있는가? Stablility: 가령 와 같은 리스트가 있다고 하면, 정렬한 뒤에도 이 두 값의 위치가 변하지 ...