![]()
분류: DFS, 백트래킹 / 문제 문제 링크 문제 설명 한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다. cdef ...f ..ef ..gh cdeh cdej ...f bT.. .T.e .Td. .Tfe bTfg bTfi .Tde a... abcd abc. abcd a... a.gh abc. 거리 : 6 6 6 8 8 10 6 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인..
![]()
타요의 예약 시스템 저희 프로젝트 타요에서 핵심 기능을 하나만 뽑으라면 뭐니 뭐니 해도 예약일 것입니다. 저희의 예약 시스템을 간략하게 설명드리면 아래와 같습니다. 차를 빌려주는 사람(이하 호스트)은 본인 차량의 예약 가능 기간을 설정할 수 있다. 차를 빌리는 사람(이하 게스트)은 해당 차량의 예약 가능 기간안에서 예약할 수 있다. 모든 예약은 해당 차량의 예약 가능 기간 중 한 구간에 완전히 포함되어야 하며 서로 겹치는 날짜가 있어서는 안 된다. 이렇게 적고 보니 알고리즘 문제 같네요. 에어비앤비의 예약 시스템과 굉장히 비슷합니다! 저희는 위 문제에 맞는 DB 구조에 대해서 비교적 오랜 시간 고민했고 결론을 내린 후에도 몇 번의 변경이 있었습니다. 개인적으로 정말 재밌었던 경험이었고 `진짜_최종_결론`..
![]()
이번 글에서는 MySQL에서 공간 데이터를 다루는 법을 알아보고 실습을 통해 성능을 비교해 본 것을 기록합니다. 특히 가장 많이 사용되는 특정 좌표로부터 특정 거리 내의 좌표를 찾는 연산을 위주로 실습하고 인덱스와 공간 연산의 성능을 테스트합니다. 들어가기 앞서 제가 이 글에서 사용한 MySQL 버전은 v8.3.0입니다. MySQL의 공간 데이터 MySQL의 `MyISAM`, `InnoDB`, `NDB`, `ARCHIVE` 스토리지 엔진은 공간 데이터 타입과 관련 함수를 지원합니다. 이 중 `MyISAM`과 `InnoDB`는 공간 데이터 타입 컬럼에 대해 공간 인덱스와 비공간 인덱스를 지원하고 `NDB`와 `ARCHIVE`는 비공간 인덱스만 지원합니다. `InnoDB`는 데카르트 SRS와 geograph..
![]()
Thread Java에서는 JDK 1.0부터 `Thread` 클래스를 제공해 멀티태스킹을 지원했습니다.(Thread) `Thread` 클래스를 통해 스레드를 생성할 수 있고 이 클래스를 상속받아 run() 메서드를 오버라이드하거나 `Runnable` 인터페이스를 구현해 `Thread` 클래스 생성자의 인자로 넘겨줌으로써 원하는 작업을 수행하는 스레드를 생성할 수 있습니다. 스레드의 상태는 다음과 같습니다. (Thread.State) New: 새로 생성된 스레드, 아직 시작되지 않음 Runnable: 실행 가능 혹은 실행 중인 상태 Blocked: 동기화에 의해 차단됨 Waiting: 다른 스레드가 특정 액션을 수행하길 기다림 Timed Waiting: 지정된 시간 동안 기다림 Terminated: 실행 ..
![]()
현대자동차 소프티어 부트캠프 3기 교육이 시작된 지 2주 정도의 시간이 지났습니다. 소프티어 OT를 기다리던 날이 엊그제 같은데 벌써 2주라니... 2주 동안 해가 바뀌며 저의 생일이 있었고 소프티어 교육에서는 3번의 조편성과 한 번의 프로젝트, 디자인과 기획 그리고 GA에 대한 교육이 있었습니다. 앞으로 남은 교육 또한 빠르게 지나갈 거라는 생각이 들어 새삼 밀도 높은 시간을 보내야 할 것 같다는 생각이 들었습니다. 남은 시간 후회 없이 보내고자 다음 교육 시작 전에 지금까지의 기간을 회고하고자 합니다. 회고 전에 앞서 제가 소프티어 부트캠프를 신청할 당시 제가 정한 목표는 "좋은 사람들을 많이 만나 많은걸 배우자"입니다. 물론 취업 연계를 통한 현대자동차 입사가 가장 중요하고 이루고 싶은 목표이고 이..
![]()
이번 글에서는 macOS에서 JDK 버전 관리 방법을 다룹니다. nodejs에서는 `n` 혹은 `nvm`과 같은 버전을 관리 툴을 사용하면 손쉽게 새로운 버전을 확인, 설치할 수 있고 설치된 버전을 변경, 삭제할 수 있습니다. java에서는 설정할 것이 노드에 비해 더 많기 때문에 미래의 저와 다른 분들에게 도움이 되고자 블로그에 정리해 봅니다. 이 글은 설정 과정과 이유를 담고 있습니다. 빠르게 설정만 필요하신 분들은 글 아래의 `정리` 부분을 바로 읽으시면 시간을 아끼실 수 있습니다. Homebrew 설치 `Homebrew`는 macOS의 오픈소스 패키지 관리 시스템입니다. CLI기반 툴이라 처음 사용하시면 어색할 수 있지만 JDK 버전 관리 글을 읽고 있는 분이라면 익숙하실 거라 생각합니다. hom..
![]()
문제: 백트래킹, BFS, 시뮬레이션 / 문제 문제 링크 문제 설명 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다. 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟..
![]()
분류: BFS, 백트래킹, 시뮬레이션 / 문제 문제 링크 문제 설명 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다. 평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다. 경재 씨는 한 걸음에 상하좌우에 인접한..
![]()
분류: 트리 구현, 그래프 탐색, 트리 순회 / 문제 문제 링크 문제 설명 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 3..
![]()
분류: 이분 탐색, 백트래킹 / 문제 문제 링크 문제 설명 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이 #include #include using namespace std; int N, S; int num[40]; long long ans; map memo; void BackTracking(bool ..
![]()
분류: BFS, 시뮬레이션, 백트래킹, 완전탐색 / 문제 문제 링크 문제 설명 길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다. 인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다. 아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다. 초록색 배양액과..
![]()
분류: 백트래킹 / 문제 문제 링크 문제 설명 세로 R$R$칸, 가로 C$C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R$R$과 C$C$가 빈칸을 사이에 두고 주어진다. (1≤R,C≤20$1 ≤ R,C ≤ 20$) 둘째 줄부..
