본문 바로가기

전체 글144

[pg] 프로그래머스 호텔 대실 1. 문제 정의 이차원 배열로 각 고객들이 호텔에 입실한 시간과 퇴실한 시간들이 주어진다. ex) [[10:00, 12:00], [11:00, 12:00]] 퇴실시 청소시간은 10분이 걸리며 이후에 방을 다시 고객에게 제공 가능하다. 위와 같은 배열이 주어질 때 가장 최소한의 방을 사용하여 고객에게 방을 제공한다고 했을 때 그 값을 구하는 것. 2. 내가 한 시도 문제를 봤을 때 이전에 풀었던 요격시스템 문제와 비슷하다고 생각했다. 대신에 다른 점이 있다면 이전에는 그냥 숫자로 풀었다면 지금은 문자열 + 시간계산이 들어갔다는 정도이다. 처음에는 문자열을 아예 시간으로 바꾼 다음에 정렬을 해서 풀려고 했지만, 문자열을 이용해서 정렬하고, 나중에 퇴실시간만 시간계산하는 것이 좀 더 코드가 간결하고 간단할 것.. 2023. 8. 24.
[pg] 프로그래머스 무인도 여행 1. 문제 정의 전형적인 bfs / dfs 문제. 맵이 주어지고 맵 안에는 무인도와 바다가 있으며, 바다칸에는 X, 무인도칸에는 1~9의 숫자가 주어진다. 무인도가 인접해 있다면 하나의 무인도라고 정의한다. 최종적으로는 맵 안에 있는 무인도들이 가지고 있는 식량들의 값을 오름차순으로 정렬해서 리턴하는 문제이다.(무인도의 갯수는 0~N) 무인도가 없을 경우에는 -1을 리턴한다. 2. 내가 한 시도 처음 문제를 보고 전형적인 bfs / dfs 문제라는 것을 깨달았다. 나같은 경우는 dfs보다는 bfs로 문제를 푸는 것이 편해서 bfs로 풀기로 결정하고, 로직을 작성했다. 이 문제의 특징이라고 할 수 있는 것은 이전에 탐색했던 루트를 다시 탐색하지 않기 위해서 visited를 전역변수로 공유해서 사용해야 했던.. 2023. 8. 24.
[면접을 위한 CS 전공지식 노트][DB] 데이터 베이스 기본 1. 데이터 베이스 일정한 규칙에 따라 구조화되어 저장되어 있는 데이터의 모음. 2. DBMS(DataBase Management System) 데이터베이스를 생성, 조작, 관리하는 역할을 한다. 데이터를 query language를 통해서 삽입, 조회, 수정, 삭제할 수 있다. DBMS는 데이터베이스 시스템의 핵심 부분으로 사용자와 응용프로그램이 데이터를 효율적으로 조작, 관리할 수 있도록 응용프로그램과 데이터베이스 사이에서 인터페이스 역할을 한다. 3. 엔티티(데이터베이스에 저장하려는 실제 항목을 나타내는 추상적인 개념) 엔티티는 데이터베이스에서 현실 세계에서 식별가능한 하나의 객체, 사물, 개념 또는 사건을 나타내는 추상적인 개념이다. (객체지향에서 설명하는 객체와 비슷하다.) 데이터베이스 내에서 .. 2023. 8. 18.
[면접을 위한 CS 전공지식 노트][자료구조] Hash Table 1. 해시 테이블이란? 해시 테이블은 데이터를 효율적으로 저장하고, 검색하기 위한 자료구조로 키(key)와 값(value)을 쌍으로 하여 데이터를 관리한다. 해시테이블은 해시 함수를 사용하여 키를 해시값으로 변환하고 이를 기반으로 저장할 배열의 인덱스를 결정하여 데이터를 저장하거나 검색한다. - 해시 테이블의 주요 특징 1) 해시 함수: 해시테이블은 해시 함수를 이용하여 키를 해시 값으로 변환한다. 해시 함수는 임의의 길이를 가진 데이터를 고정된 길이의 값으로 매핑하는 함수이다. 이 때 동일한 키는 항상 동일한 해시값으로 매핑되어야 한다. 해시 값은 배열의 인덱스와 연결되며, 이를 통해 데이터가 저장되거나 검색된다. 2) 해시 충돌: 해시 함수의 특성상 서로 다른 데이터가 같은 해시 값으로 매핑 될 수 .. 2023. 8. 11.
[면접을 위한 CS 전공지식 노트][자료구조] Set 1. Set이란? 자료구조인 SET은 수학에서의 집합을 구현해놓은 것이다. 집합은 중복되지 않는 원소들의 모임으로 수학적인 집합 개념을 컴퓨터 과학의 문제에 적용하기 위해서 만들어진 자료구조 이다. Set은 다음과 같은 특징을 가지고 있다. SET의 주요 특징 1) 고유한 원소: Set은 각 원소가 중복되지 않는다. Unique한 원소. 2) 순서 없음: Set에서는 원소의 순서를 보장하지 않는다. 순서가 없다. 3) 집합 연산: Set은 원소들 간의 합집합, 교집합, 차집합 등과 같은 집합연산을 지원한다. 2. JAVA에서의 Set 1) HashSet 가장 일반적으로 사용되는 Set 구현체 이며, 해시테이블을 기반으로 구현되어 있다. HashSet의 주요 특징 - 순서를 보장하지 않는다. - 추가, 삭.. 2023. 8. 11.
[면접을 위한 CS 전공지식 노트][자료구조] Map 0. 개요 이번 글에서는 키를 통해 검색할 경우에 자주쓰는 Map에 대해서 공부한 내용을 정리하고자 한다. 나 같은 경우에는 JAVA 코딩을 할 때에 map을 사용한다고 하면 HashMap만을 그냥 사용해왔는데, 공부해보니 그 외에도 코딩할 때 사용하면 유용할만한 자바에서 제공해주는 유용한 Map들이 존재했다. 이 글에서는 그것들에 대해서 기록해놓고 계속해서 볼 수 있도록 하려고 한다. 1. Map이란? 프로그래밍을 한번이라도 접해 본 사람이라면 각각의 언어마다 부르는 이름은 조금 다를 수도 있지만, Map 형식의 데이터를 이미 다뤄봤을 것이다. Python에서는 Dictionary라는 데이터타입으로 불리우기도 하고, API를 이용해본 사람들이라면 JSON(JavaScript Object Notation.. 2023. 8. 11.
[자료구조] 힙과 우선순위 큐 1. 힙 힙은 트리 글에서 정리한 완전 이진 트리에 속하는 자료구조이다. 그래서 완전 이진 트리의 특성을 모두 지니고 있다. (완전이진트리의 특성: 모든 노드는 왼쪽 노드부터 채워져야하고, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.) 힙은 최대힙과, 최소힙이 존재한다. 최대힙(Max Heap) - 부모 노드의 값은 항상 자식보다 크거나 같다. (좌우 순서는 상관없다) - 루트 노드는 언제나 트리의 최댓값이다. - 값의 중복을 허용. 최소힙(Min Heap) - 부모노드의 값은 항상 자식보다 작거나 같다. (좌우 순서는 상관없다.) - 루트 노드는 언제나 트리의 최솟값이다. - 값이 중복을 허용. 이러한 힙은 일차원 배열로 구현이 가능하다. 인덱스 1부터 루트노드부터 값을 넣어주면 아래와 같은.. 2023. 8. 10.
[pg] 프로그래머스 두 원사이의 정수 쌍 1. 문제정의 반지름이 r1인 작은 원과, r2인 큰 원이 존재한다. 이 두 원을 겹치면 작은원과 큰원 사이에는 일부 면적이 발생한다. 이 면적안에 있는 정수로 이루어진 좌표를 구하는 문제이다. 2. 내가 한 시도 lv2로 올라오고 나서 부터는 문제를 봤을 때 어떻게 풀어야지! 라는 것이 잘 떠오르지 않게 되었다. 검색을 통해 이 문제는 피타고라스의 정리를 이용하면 쉽게 풀리는 문제라는 것을 알고나서 그 방향으로 해결법을 고민하기 시작하였다. 1번째 시도 피타고라스의 정리를 이용해서 원 안에 있는 모든 점을 서치하여 조건에 맞는 점들만 리턴하도록 코딩하였다. 말 그대로 무식하게 모든 점을 서치해봤다. 결과는 실패했다. 일부 테스트 케이스에서는 성공이었지만 일부에서는 시간초과가 발생하였다. 2번째시도 이번.. 2023. 8. 9.
[pg] 프로그래머스 요격시스템 1. 문제 정의 폭격 미사일이 하늘로 부터 수평 방향으로 s,e 구간사이에 떨어지고, 이 구간 사이에 미사일을 날려 최소한의 미사일로 폭격미사일을 막아내는 문제이다 ex) [1,2] , [3,4], [4,5], [5,10] 일 경우 총 4개의 미사일이 필요 ex) [1,5], [2,4], [5,10] 일 경우 총 2개의 미사일이 필요 2. 내가 한 시도 처음에는 감이 잡히질 않아서 서치를 해봤는데, 정렬을 하면 쉽게 풀리는 문제라는 힌트를 얻고, 그것을 통해 해결하였다. 개구간 s,e 아무거나 골라서 정렬을 하고, 순회하면서 범위내에서 해결하지 못하면 미사일을 추가하는 방식으로 푸는 방식이었다. 나 같은 경우에는 개구간 s를 기준으로 내림차순 정렬하여 풀이를 진행하였다. 3. 코드 public class.. 2023. 8. 9.

티스토리툴바