자료구조

이번 포스팅에서는 킥스타트 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)라고 한다. 무향 그래프에서 각..

오늘은 트리와 힙 자료구조에 대해서 알아보려고 한다. 트리 트리(Tree)는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 계층적(Hierarchical) 자료구조라고 표현하기도 한다. 유닉스/윈도우의 디렉터리(폴더) 구조가 대표적인 트리 구조의 예시이다. 트리와 관련된 용어들은 다음과 같다. 노드(Node) : 트리를 구성하는 기본 원소 간선(Edge) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(Siblings Node) : 같은 부모 노드를 갖는..