Algorithm
[BOJ] 백준 2812 크게 만들기 - Python/Java
문제 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 스택 자료구조와 그리디 알고리즘을 이용해서 풀 수 있는 문제입니다. N개로 이루어진 숫자 중에서 K개를 삭제해야 하고, 주어진 숫자의 순서가 변하면 안된다는 점이 스택 자료구조를 쓸 수 있는 이유가 됩니다. 그리고 각 숫자를 삭제할 것인가 말 것인가를 결정할 때 그리디(Greedy)하게 결정할 수 있죠. 우선 결과로 리턴할 문자열 s와 문제에서 주어진 숫자 Num이 있다고 해보겠습니다. 그렇다면 아래 로직에 따라 s를 만들어갈 수 있습니다. 1) s가 빈 문자열이면 무조건 현재 Num의 숫자를 더해줍니다. 2) s가 빈 문자열이..
Spring & Springboot
[스프링/Spring] 스프링 시큐리티(Spring Security) 가이드라인 따라하기
0. 소개 스프링 시큐리티는 스프링 기반의 어플리케이션의 보안(인증, 권한)을 담당하는 프레임워크입니다. 스프링 시큐리티가 없다면 자체적인 세션 체크나 리다이렉트 등의 기능 구현이 필요하죠. 스프링 시큐리티는 필터(filter) 기반으로 동작하기 때문에 spring MVC와 분리되어 관리 및 동작합니다. 이번 포스팅에서는 아래 링크의 가이드라인을 따라서 스프링 시큐리티(Spring Security)를 실습해보고, 스프링 시큐리티에 대한 기본 개념을 익혀보고자 합니다. Securing a Web Application this guide is designed to get you productive as quickly as possible and using the latest Spring project rel..
Algorithm
[BOJ] 백준 9370 미확인 도착지 - Python/Java
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net [해설] 이 문제는 다익스트라 알고리즘을 기반으로 해결할 수 있으며 기본 아이디어는 다음과 같습니다. 경로 1) (시작점 → g) + (g → h) + (h → 도착점) 경로 2) (시작점 → h) + (h → g) + (g → 도착점) 위 두 가지 경로 중에서 비용이 더 적은 경로와 (시작점 → 도착점)을 직접 구한 비용이 같다면 해당 도착점은 반드시 (g, h) 도로를 지난다고 볼 수 있..
CS/Network
[네트워크/Network] REST API와 HTTP 메서드(GET, POST, PUT, DELETE, OPTIONS, HEAD, PATCH)
1. Rest API, Restful API 정의 REST는 REpresentational State Transfer라는 용어의 약자로, 2000년도에 로이 필딩 (Roy Fielding)의 박사학위 논문에서 최초로 소개되었습니다. 로이 필딩은 HTTP의 주요 저자 중 한 사람으로 그 당시 웹(HTTP) 설계의 우수성에 비해 제대로 사용되어지지 못하는 모습에 안타까워하며 웹의 장점을 최대한 활용할 수 있는 아키텍처로써 REST를 발표했다고 합니다. 조금 더 현실적인 관점에서 REST API를 정의하자면, REST API는 웹 상에서 사용되는 여러 리소스를HTTP URI로 표현하고 해당 리소스에 대한 행위를 HTTP Method로 정의하는 방식을 말합니다. 그리고 RESTful API는 REST API 설..
CS/Database
[데이터베이스/DB] 관계형 DB에서 JOIN의 개념(Inner join과 Left join)
1. JOIN ? JOIN이란 영어 해석 그대로 두 개 이상의 테이블을 결합하여 데이터를 조회할 때 쓰는 개념입니다. 정규화를 통해 여러 테이블로 나누어진 데이터는 서로 연관관계를 가지고 있을 수 있고, A라는 엔티티를 조회할 때 B라는 엔티티의 부분 정보도 같이 조회하고 싶다면 JOIN 개념이 반드시 필요하죠. 어떻게 보면 JOIN이 필요한 이유는 정규화로부터 파생되었다고 볼 수 있기 때문에, 정규화 개념은 JOIN을 공부하기 이전에 반드시 알아야하는 내용이기도 합니다. 본론으로 돌아와서, JOIN의 예시를 하나 보겠습니다. 위 내용은 게시물(Post)을 조회할 때 게시물을 작성한 유저의 정보와 해당 게시물에 관련된 '좋아요' 정보를 함께 불러오는 JPQL 쿼리입니다. 정규화 과정에 의해 DB 스키마는..
Algorithm
[BOJ] 백준 15685 드래곤 커브 - Python/Java
15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제를 한 두 세번정도 읽으면서 이해를 하고, 그대로 구현해주면 되는 문제입니다. 다만, 이 문제에서 X가 증가하는 방향이 오른쪽이고, Y가 증가하는 방향이 아래쪽이라는 점에서 일반적인 이차원 리스트의 인덱싱과 조금 다른데요. 이 부분은 X, Y를 그냥 바꿔서 생각하면 됩니다. 그런데 저는 그냥 있는 그대로 X, Y를 사용했습니다. 한편, 이 문제의 핵심은 "이전 세대의 드래곤 커브가 현재 세대의 드래곤 커브를 만드는 데 사용된다"는 점..
Algorithm
[BOJ] 백준 1915 가장 큰 정사각형 - Python/Java
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이 문제를 직관적으로 생각해보면 아래와 같은 완전탐색에 대한 아이디어를 떠올릴 수 있습니다. "이차원 배열에 존재하는 모든 점에 대해 해당 지점을 오른쪽 아래 모서리라고 생각한 뒤, 정사각형 길이를 1부터 늘려나가보면서 이전 지점들을 탐색하고, 모두 1로 채워져있으면 정사각형 크기를 갱신한다." 하지만 이 방식으로 문제를 해결하면 결국 맨 끝의 점에서는 시간복잡도가 O(N^3)에 가까워지는 것을 예상할 수 있습니다. 따라서, 이 문제는 위의 정의를 바탕으로 DP를 이..
CS/Network
[네트워크/Network] 비연결형 트랜스포트 UDP 정리
💡0. 들어가면서 이전 포스팅에서 OSI 7계층에 대해 정리를 했었는데요. 트랜스포트 계층의 기본적인 역할은 네트워크 계층과 애플리케이션 레벨 프로세스 간의 데이터를 넘겨주기 위해서 다중화와 역다중화 서비스를 제공하는 것이었습니다. [네트워크/Network] 네트워크의 기본: OSI 계층 구조와 캡슐화 🤔 0. 개요 "OSI 7계층이 무엇인가요?" "컴퓨터 네트워크를 왜 7계층으로 나누나요?" "메시지, 데이터그램, 세그먼트의 차이와 캡슐화는 무엇인가요?" CS를 공부해본 사람이라면 한 번쯤은 OSI 7계층 studyandwrite.tistory.com 이 내용을 간단하게 복기해보면, 애플리케이션 계층은 트랜스포트 계층에 '메시지(Message)' 형태로 데이터를 전달해주고, 트랜스포트 계층은 이를 '세..
CS/Network
[네트워크/Network] IPv4 주소 체계와 DHCP
1. 용어 정리 지난 포스팅에서는 IPv4 데이터그램의 포맷과 단편화에 대한 공부를 했고, 이번 시간에는 IPv4 주소체계에 대해서 공부를 해보려고 합니다. 본격적인 논의를 하기에 앞서, 호스트와 라우터가 인터넷에 연결되는 방식에 관한 몇 가지 단어를 정의해보려고 하는데요. 호스트는 일반적으로 네트워크와 연결되는 하나의 링크를 가집니다. 호스트 IP는 이 링크를 통해 데이터그램을 보내게 되며, 이 때 호스트와 물리적 링크 사이의 경계를 "인터페이스"라고 합니다. 한편, 라우터의 작업은 한 링크로부터 데이터그램을 수신하여 다른 링크로 전달하는 것이므로 라우터는 2개 이상의 연결된 링크가 필요합니다. 라우터와 이런 링크 사이의 경계 또한 인터페이스라고 하며 각 링크마다 하나의 인터페이스를 가지고 하나의 라우..
Algorithm
[BOJ] 백준 18119 단어 암기 - Python/Java
https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 해설 비트마스킹을 이용해서 풀 수 있는 전형적인 문제입니다. 문제에서 주어지는 영어 단어는 모두 소문자로만 주어지기 때문에, 이 문제에서 다뤄야 할 모든 알파벳 경우의 수는 26가지입니다. 따라서 모든 알파벳을 다 알고 있는 경우를 11111111111111111111111111, 모든 알파벳을 모두 모르는 경우를 00000000000000000000000000이라고 표현할 수 있죠. 그리고 ..
