자료구조

최근에 Typescript로 BST를 직접 구현해 보라는 질문을 받았는데 제대로 구현하지 못했다. 그래서 중요한 개념을 복습할 겸 하나씩 정리해 보고자 한다. with Codex이 글은 정수 값만 저장하는 Binary Search Tree(BST) 를 TreeNode, BinarySearchTree 두 클래스로 직접 구현하는 흐름을 정리한 노트입니다. 먼저 의사코드로 생각을 고정하고, 그 다음 그림으로 포인터 이동을 확인한 뒤, 마지막에 TypeScript 코드로 옮깁니다.이 구현의 규칙은 네 가지입니다.value는 정수만 허용합니다.한 노드의 왼쪽 서브트리에는 더 작은 값만 둡니다.한 노드의 오른쪽 서브트리에는 더 큰 값만 둡니다.중복 값은 삽입하지 않고 false를 반환합니다.1. BST 규칙부터 잡..

이번 포스팅에서는 킥스타트 2020 Round C에 대한 문제 풀이를 공유하고자 한다. 1. Countdown 간단한 배열 문제이다. 배열의 반복문을 돌면서 주어진 숫자부터 시작되는 카운트 다운이 총 몇 개인지를 세어 주면 된다. 한 번 배열을 순환해서 답을 구할 수 있기 때문에 시간복잡도는 O(N). 2. Stable Wall 그래프 개념을 가지고 풀어야 하는 조금 까다로운 문제이다. 나의 경우 다른 사람의 풀이를 조금 참고하면서 풀었다. 문제를 이해하는 것 부터 쉽지가 않았던 것 같다. 위상 정렬(topological sort)과 DFS를 사용하였다. N개의 폴리노미노(polynomino)가 있고 이것들이 stable한 경우, 즉 각각의 폴리노미노가 바닥에 붙어 있거나, 다른 폴리노미노 위에 올라타 ..

중견기업 이상에서 많이 물어보는 CS 기본기 인터뷰 질문 중 첫 번째로 자료구조에 대해서 정리해 보려고 한다. 자료구조 Array와 LinkedList의 차이가 무엇인가요? (N사 전화면접) Array는 Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)이다. 반면 Linkedlist는 Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(N)이다. 저장방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다. 반면 Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다...

이번에 살펴볼 문제는 프로그래머스의 문제이다. https://programmers.co.kr/learn/courses/30/lessons/62049 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 종이를 계속 반으로 접어서 안으로 파인 부분(∨)은 0, 밖으로 볼록 튀어나온 부분(∧)은 1로 순서대로 출력하면 되는 문제이다. 이 문제는 규칙성을 찾고 적절한 자료구조를 찾아서 탐색하면 그렇게 어렵지 않게 풀 수 있는 문제이다. 다만, 개인적으로 처음에 생각하기가 조금 쉽지 않았던 것 같다. 한 번 ..

오늘 살펴볼 문제는 카카오 19년 겨울인턴 코딩테스트 4번 문제이다. https://programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오는 매번 코딩테스트마다 문제 해설을 자사 블로그에 공개한다. 관심있는 분들은 읽어 보아도 좋을 것 같다. 2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 – tech.kakao.com “2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난..

오늘 살펴볼 문제는 백준 9202번 문제이다. https://www.acmicpc.net/problem/9202 9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다. Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지 www.acmicpc.net 사실 이 문제는 굉장히 어려웠다. 그래서 나는 다른 분의 코드를 어느정도 참고해서 풀었다..

오늘 살펴볼 문제는 백준 1655번 문제이다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다. N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나? 라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)..

이번 포스팅에서는 그래프 자료구조에 대해서 공부해 본다. 그래프 그래프(Graph)는 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있다. 예를 들면 지하철에서 다른 역으로 가는 최단 경로를 찾아주는 서비스도 그래프 알고리즘을 사용한다. 그래프의 한 종류로 트리 자료구조가 있는데 그래프와 트리의 차이는 다음과 같다. 그래프 관련 용어를 정리하면 다음과 같다. 먼저 정점과 간선의 연결 관계에서 방향성을 가지는 지를 가지고 나누어 볼 수 있다. 방향성이 없는 그래프를 무향 그래프(Undirected Graph)라 하고, 방향성이 포함되어 있는 그래프를 유향 그래프(Directed Graph)라고 한다. 무향 그래프에서 각..