![]()
분류: 백트래킹 / 문제 문제 링크 문제 설명 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다. 정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 ..
![]()
분류: MST, 크루스칼 알고리즘 문제 문제 링크 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 ..
![]()
구글이 리눅스 커널 패치를 통해 TCP 통신 성능을 40%까지 향상할 수 있었다는 것을 알게 됐습니다. 어떻게 했길래 40%라는 수치가 나오는지 궁금해서 알아보았고 아주 단순하고 그냥 지나칠 수 있는 기본 지식을 실제로 적용하는 것이 성능에 크게 영향을 미칠 수 있다는 사실이 놀라워 글로 작성해 봅니다. 원본 아티클: Linux 6.8 Network Optimizations Can Boost TCP Performance For Many Concurrent Connections By ~ 40% 유튜브 영상: Google Patches Linux kernel with 40% TCP performance - Hussein Nasser 구글은 어떻게 성능을 향상했는가? 구글은 리눅스 커널의 TCP 성능을 향..
![]()
분류: 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..
