Algorithm
[프로그래머스(Python/Java)] 땅따먹기
https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 이 문제는 각 행의 원소 개수가 4개로 고정되어 있고, 행을 한 칸씩 내려갈 때 그 이전 행과 동일한 열을 선택할 수 없는 조건만 존재합니다. 완전 탐색으로 모든 경우를 보기 위해서는 O(3^N) 만큼의 시간 복잡도가 소요되기 때문에 제한된 시간 안에 문제를 해결할 수 없습니다. *시간 복잡도가 O(3^N)인 이유는 각 행을 내려갈 때마다 3..
Spring & Springboot
[스프링/Spring] 연관관계를 갖는 DTO를 엔티티로 저장할 때 고민
💡 문제 상황 만들어보고 있는 프로젝트에서는 '유저', '게시물', '카테고리'라는 도메인이 존재합니다. 이 때 유저와 게시물은 일대다관계, 카테고리와 게시물도 일대다관계를 가지고 있는데요. 다른 도메인이나 서비스에 대한 로직은 차치하고 말씀드리겠습니다. 문제가 되는 상황은 사용자가 게시물을 작성하는 상황에서 발생했는데요. 아래는 게시물 작성과 관련된 Controller, Service, Post 엔티티, PostSaveDTO입니다. PostSaveDTO는 게시물을 작성할 때 JSON 데이터를 객체로 입력받아 서비스 로직에 던져지는 녀석입니다. 문제는 어떤 사용자가 게시물을 작성한다고 가정했을 때, Json 형태로 받아올 수 있는 정보는 유저 정보, 카테고리의 아이디, 게시물의 제목과 내용이라는 점에서 ..
Algorithm
[BOJ] 백준 1914 하노이탑 - Python/Java
https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 해설 이 문제가 실버2인 이유는 아마 대중적으로 알려진 문제라서 그렇지 않을까 생각합니다. 혼자서 풀려고 했을 때는 정말 모르겠어서 다른 사람들의 풀이를 참고해서 이해할 수밖에 없었습니다...☹️ 하노이탑 문제의 핵심 아이디어는 원반 N개 문제를 해결하기 위해서는 원반이 N-1개인 문제를 해결하면 된다는 것인데요. 구체적으로 풀어서 이야기해보면 아래와 같습니다. 1) N개의 원반이 주어지면 위에서부..
CS/Network
[네트워크/Network] 웹 캐시(Web Cache; 프록시 서버)를 통한 응답 속도 향상 원리 이해하기
💡 0. 웹 캐시? 웹 캐시(Web cache; 프록시 서버)는 원출처의 웹 서버를 대신하여 HTTP 통신을 대신하는 네트워크 개체입니다. 웹 캐시는 자체의 저장 디스크를 가지고 있어서 최근 호출된 객체의 사본을 저장 및 보존하고 아래 그림처럼 모든 브라우저는 사용자의 모든 HTTP 요구가 웹 캐시에 가장 먼저 보내지도록 구성될 수 있습니다. 이 때, 리버스 캐싱(Reverse Caching)이란 웹 서버로 유입되는 HTTP 트래픽을 캐싱 시스템이 저장하고 있다가 동일 요청이 들어왔을 때 캐싱 시스템이 이 데이터를 돌려줌으로써 빠른 응답 성능을 제공하는 방법을 말하는데요. 위 그림에서 사용자가 'http://www.xxxx.com/someImage.png '라는 객체(데이터)를 요구한다고 해봅시다. 그러..
Algorithm
[백준(Python/Java)] 6497_전력난
6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 이 문제는 도시의 모든 집을 연결할 수 있는 최소한의 간선(길)만을 선택하는 문제로, 최소 스패닝 트리(Minimum Spanning Tree, MST)를 이용해 풀 수 있습니다. MST를 구현하는 방법에는 우선순위 큐를 이용하는 방법, 크루스칼 알고리즘을 이용하는 방법과 프림 알고리즘을 이용하는 방법이 있는데요. 이 문제에서는 MST에 보편적으로 쓰이는 크루스칼 알고리즘을 이용해 해결했습니다. 개별 간선(Edge)은 해당 길의 비용과 이어진 두 마을(정점)의 정보를 가지..
Algorithm
[백준(Python/Java)] 2458_키 순서
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net * 프로그래머스에 있는 [순위] 문제와 완전히 동일한 문제인데요. 해당 문제의 링크는 아래에 있습니다. 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 우선 이 문제에서 "자신의 키가 몇 번째인지 정확히 알 수 있는 사람"은 자신을 제외한 나머지 사람들이 자신보다 키가 큰지, 작은지를 모두 아는 사람입니다. 만..
Spring & Springboot
[스프링/Spring] @OneToMany/@ManyToOne 연관관계에서의 Infinite Recursion 문제를 DTO로 해결하기
🧐 문제 상황 투표 기능 API를 만들다가 마주했던 문제인데요. 아래와 같이 Vote, VoteOption이라는 두 개의 도메인이 존재합니다. Vote 도메인은 '투표'라는 엔티티를 의미하며 어떤 게시물(Post)에 종속되어 있고 여러 개의 투표 항목 옵션(VoteOption)과 일대다 관계로 매핑되어 있습니다. 하나의 투표에는 선택할 수 있는 투표항목이 여러 개 존재하기 때문이죠. 그리고 VoteOption은 한 개의 Vote에 여러 개가 존재하므로 @ManyToOne 어노테이션으로 Vote를 참조합니다. 이 상황에서 "어떤 게시물에 존재하는 투표를 조회하는" API를 작성하려고 합니다. Request-Header로 조회한 유저의 아이디를 받고, 게시물의 아이디와 투표의 아이디를 PathVariable..
CS/Database
[데이터베이스/DB] 키(Key)의 종류와 개념
1-1. 들어가면서 데이터베이스는 수 많은 테이블과 그 안의 데이터들로 구성되어 있습니다. 그리고 그 테이블은 정렬되지 않고 조직화되지 않은 수천 개, 수만 개의 레코드로 확장되어 있습니다. 이러한 테이블 속에서 특정 레코드를 가져오려면 그 레코드를 유일하게 식별할 수 있는 조건으로 조회하는 작업이 필요한데요. 이 때 필요한 개념이 데이터베이스에서 키(Key)이며, 이번 시간에는 여러가지 키에 대한 개념에 대해 정리해보겠습니다. 우선 키의 정의는 아래와 같습니다. 키(Key): 관계형 데이터베이스(RDBMS)에서 테이블 관의 관계를 설정 및 식별하고, 테이블 내부의 레코드를 고유하게 식별하는 데 사용할 때 사용하는 속성 그리고 밑에서 강한 엔티티 타입과 약한 엔티티 타입을 설명하면서 부분키(Partial..
Algorithm
[백준(Python/Java)] 14890_경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 해석을 잘못해서 엄청나게 복잡한 코드를 생각했었는데요. 처음에 이 문제를 봤을 때는 "가로로 설치한 경사로와 세로로 설치한 경사로가 겹치면 어떻게 하지?"에 대한 처리를 엄청 고민했습니다. 하지만 이 문제는 가로와 세로에 설치한 경사로를 따로 구분해서 푸는 문제이기 때문에 위와 같은 상황은 고려하지 않아도 되는 것이었죠. 따라서 이 문제는 매우 간단해집니다. 주어진 이차원 배열의 모든 행과 열을 탐색해보면서 해당..
CS/OS
[운영체제/OS] 동기화 이슈 처리하기 - (2)
💡 1. High-level Synchronization ? 예전 포스팅에서 Software-only solution(피터슨 알고리즘)과 Hardware Atomic solution(Test-and-Set, Swap)으로 동기화 이슈를 처리하는 방법에 대해 공부해봤는데요. * 해당 부분에 대한 포스팅이 궁금하신 분은 아래 링크에서 확인해주세요. [운영체제/OS] 동기화 이슈 처리하기 - (1) 0. 문제 상황 // Producer = 데이터를 추가하는 역할(counter 증가) register A := counter; // load register A := registerA + 1; // add counter := registerA; // store // Consumer = 데이터를 빼는(소모하는.. s..
