스파르타 내일배움캠프/Data Structure & Algorithm(7)
-
7일차: 기업 코딩 테스트 풀이
삼성 역량 테스트 - 2 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으..
2022.11.18 -
6일차 : 기업 코딩테스트 풀이(2)
삼성 역량 테스트 - 1 Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진..
2022.11.16 -
5일차 : 기업 코딩테스트 문제 풀이(1)
테스트 문제 풀이는 혼자서 풀지 못하고, 스파르타 알고리즘 강의의 도움을 받아 풀이를 진행하였습니다. 실전 문제 풀이에 앞서서 마음가짐 - 1 실전 알고리즘 문제에서는 이 문제를 어떤 개념으로 풀 건지 알려주지 않고 문제를 냅니다! 즉, 문제를 읽으면서 이 문제는 어떤 자료 구조를 쓰는 게 좋을지, 어떤 알고리즘이 좋을지 고민해야 됩니다. 문제의 특성과 입력값, 출력값들을 보시면서 디버깅을 합니다. 실전 문제 풀이에 앞서서 마음가짐 - 2 실전 알고리즘은 문제부터 이해하기 힘든 경우가 많습니다. 그래서 문제의 일부분씩 이해하시거나 예제를 써보시면서 이해하시는 게 좋습니다! 최소 10분~20분은 문제를 자세하게 이해하시고 풀어봐야 합니다. 2019년 상반기 LINE 인턴 채용 코딩테스트 Q. 연인 코니와 ..
2022.11.15 -
4일차 : 과제
Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환하시오. dates[i]에는 i번째 공급 가능일이 들어있으..
2022.11.14 -
3일차 : 큐, 해쉬, 힙, BFS, DFS, Dynamic Programming
오늘은 알고리즘 공부만 진행하였습니다. 다음주 자바 수업과 알고리즘을 병행할 때 뒤처지지 않도록 열심히 달렸습니다! 1. Queue 큐라는 자료 구조에서 제공하는 기능은 다음과 같습니다! enqueue(data) : 맨 뒤에 데이터 추가하기 dequeue() : 맨 앞의 데이터 뽑기 peek() : 맨 앞의 데이터 보기 isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기 큐는 뭘로 구현하면 좋을까요? 데이터 넣고 뽑는 걸 자주하는 자료 구조입니다! 그렇습니다. 스택과 마찬가지로 링크드 리스트와 유사하게 구현할 수 있습니다! 이 때, 스택과 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야 하므로, self.head 와 self.tail 을 가지고 시작합니다! 큐의 구현 class Node: ..
2022.11.12 -
2일차 : 이분탐색, 재귀, 정렬, 스택
오늘은 두가지(이진, 순차) 탐색을 구현하고 시간 복잡도를 비교 재귀 함수 구현 및 문제 풀이 버블, 선택, 삽입, 병합 정렬 구현 및 문제 풀이 스택 구현 및 문제 풀이 를 진행하였습니다. 1. 탐색 이진 탐색 vs 순차 탐색 Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다. 이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오. 순차 탐색 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_sequential(target, array): for number in array: if targe..
2022.11.11