Algorithm
[BOJ] 백준 1759 암호 만들기 - Python/Java
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해설 주어진 문자열의 길이가 최대 15밖에 되지 않기 때문에 모든 경우를 완전탐색할 수 있는 문제입니다. 다시 말해서, 각 문자를 비밀번호에 포함/미포함으로 완전 탐색을 해도 2^15번만에 모든 경우를 탐색할 수 있는 것이죠. 구체적으로 문제의 조건을 들여다보겠습니다. 문제에서는 비밀번호가 "1) 사전식으로 오름차순 정렬되어 있다. 2) 자음의 개수는 2자 이상이다. 3) 모음의 개수는 1자 이상이다...
CS/Database
[데이터베이스/DB] 데이터베이스에서 인덱스(INDEX)의 사용
0. 들어가면서 인덱스(Index)는 데이터베이스에서 테이블의 조회 속도를 높여주는 자료구조를 말합니다. 조회 성능의 관점에서 인덱스의 사용은 데이터베이스 안의 레코드를 처음부터 풀스캔(Full Scan)하지 않고, 테이블 내의 컬럼을 색인화하여 B+ Tree로 구성된 구조를 만들고 INDEX 파일 검색으로 속도를 향상시키게 됩니다. 사실 인덱스 자체에 대한 개념은 평소에 우리가 무의식적으로 계속 사용하고 있습니다. List objects = ... Object o = objects.get(index); ... 위와 같이 리스트에서 어떤 자료를 뽑을 때 처음부터 하나하나 세서 해당 위치에 있는 자료를 뽑는 것이 아니라, 인덱스로 바로 접근하여 해당 위치의 데이터를 꺼내오고 있죠. 그렇다면 데이터베이스에서..
Algorithm
[BOJ] 백준 1405 미친 로봇 - Python/Java
https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 해설 깊이 우선 탐색을 이용해서 방문했던 곳을 다시 방문하지 않는 조건으로 모든 지점을 완전 탐색하는 문제입니다. 깊이 우선 탐색을 이용해서 네 방향으로 N번 이동하게 될 때, 가능한 총 경우의 수는 4^N입니다. 따라서 문제에서 주어진 N
Spring & Springboot
[스프링/Spring] 스프링 MVC? DispatcherServlet 이해하기
0. 들어가면서 이전에 작성했던 포스팅에서는 스프링 MVC 프레임워크의 기초가 되는 FrontController(프론트 컨트롤러) 패턴에 대해 공부했습니다. 프론트 컨트롤러는 통해 개별 컨트롤러가 공통적으로 수행해야 하는 로직을 없애줄 수 있었고, 개별 컨트롤러가 일일이 서블릿의 request, response를 핸들링할 필요가 없게 만들어주었습니다. 그리고 이번 포스팅에서 자세히 다뤄볼 DispatcherServlet은 이러한 FrontController 패턴을 그대로 받아들여 스프링 MVC 프레임워크에서 발전시킨 개념입니다. 1. 스프링 MVC의 구조 아래 그림은 스프링 MVC 구조를 보여줍니다. DispatcherServlet이 어떤 역할을 하는지 이해하기 위해서 위 구조에 대해 간략하게 설명을 해..
Algorithm
[BOJ] 백준 10942 펠린드롬? - Python/Java
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 해설 이 문제를 풀 때 가장 중요한 포인트는 두 가지라고 생각합니다. 1. 문제에서 주어진 각 숫자 자체는 팰린드롬 수가 아니어도 된다는 것 2. DP 메모이제이션의 순서를 고민해봐야 한다는 것 - 먼저 이 문제에서 팰린드롬인지를 확인할 때는 입력으로 주어진 개별 숫자가 팰린드롬인지의 여부는 관계가 없습니다. 즉, 입력이 123, 123 이렇게 두 수가 들어왔다고 하면, 123 / 123은 팰린드롬이 되는 것입니다. 저는 맨 처음에 각..
Spring & Springboot
[스프링/Spring] FrontController 패턴과 스프링 MVC
0. 들어가면서 스프링 MVC 프레임워크의 핵심은 모델(Model), 뷰(View), 컨트롤러(Controller)입니다. 어떻게 보면 이 세 가지 요소가 스프링 MVC 자체를 의미한다고 볼 수도 있죠. 그런데, 이를 역으로 생각해보면 스프링 MVC 프레임워크가 자리 잡기 전에는 개발을 할 때 여러 문제점이나 어려움이 있었다는 뜻이겠죠. 그래서 이번 포스팅에서는 이러한 문제점들을 진단해보고, 스프링 MVC 프레임워크가 어떤 원리로 동작하는지 FrontController 패턴과 함께 살펴보려고 합니다. 특히, 어떤 어노테이션이나 다른 스프링의 기능없이 다형성을 적극 활용해서 스프링 MVC 프레임워크를 따라해보겠습니다. 이를 경험해보면 스프링 MVC가 어떤 원리로 동작하는지를 이해하는 데 도움이 되리라 생각..
Algorithm
[BOJ] 백준 2668 숫자고르기 - Python/Java
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 해설 깊이 우선 탐색을 이용해서 싸이클을 판별하는 문제입니다. 아래와 같이 입력이 주어졌다고 해보겠습니다. 1 2 3 4 5 6 7 3 1 1 5 5 4 6 그러면 윗줄의 각 번호를 하나의 노드라고 생각하고, 아랫줄의 각 번호를 해당 노드에서 도착할 수 있는 노드라고 이해할 수 있습니다. 이 때, 1번 노드에서 출발한다고 하면 1 → 3 → 1 과 같은 싸이클이 만들어지는데요. 싸이클..
Spring & Springboot
[스프링/Spring] 서블릿(Servlet)과 서블릿 컨테이너
0. 들어가면서 자바 웹 기술 역사를 살펴보면 서블릿은 JSP보다도 이전에 생긴 근본적인 개념입니다. 아래에서 서블릿에 대해 자세히 기술하겠지만, 서블릿을 공부하다보면 그 당시 개발자들이 서블릿'만'으로 개발을 하면서 얼마나 고통받았을지 안타깝기도 합니다. 아무튼 서블릿에 대해 공부한다는 것은 현재 스프링 MVC 패턴의 필요성과 MVC 패턴이 서블릿을 활용하여 어떻게 수많은 기술적 어려움을 쉽게 풀어냈는지를 이해하는 데 도움이 되리라 생각합니다. 1. 서블릿(Servlet) 자바 서블릿(Java Servlet)은 자바를 사용하여 웹페이지를 동적으로 생성하는 서버측 프로그램을 말하는데요. 쉽게 이야기하면, 클라이언트가 서버에 요청을 보낼 때와 응답을 받을 때 필요한 HTTP 작업을 도와주는 녀석이 서블릿입..
Java & Kotlin
[Java] 자바 람다식과 함수형 인터페이스(Functional Interface) - (1)
1. 들어가면서 - 람다식이란? 이번 시간에는 크게 네 가지 주제, [1] 람다식이란 무엇인가 [2] 어떻게 작성하는가 [3] 어떻게 동작하는가 [4] 어떻게 활용하는가에 대해 설명해보겠습니다. 보통 객체지향적 프로그래밍을 한다는 것은 프로그램 안에서 상호작용하는 객체들을 중심으로 객체가 가지는 값이나 행위들로 프로그램을 끌고 나가는 것을 말합니다. 반면, 함수형 프로그래밍은 프로그램을 상태값을 지니지 않는 함수값들의 연속으로 생각할 수 있게 해주는 방법을 말하죠. 이러한 관점에서 바라볼 때, JDK1.8에서 도입된 람다식(Lambda Expression)은 메서드를 하나의 식(expression)으로 표현할 수 있게 하여 자바가 객체지향언어인 동시에 함수형 언어의 속성을 갖게 해주었습니다. 뒤에서도 살..
Algorithm
[BOJ] 백준 11578 팀원 모집 - Python/Java
https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 해설 조합을 이용한 완전탐색, 그리고 비트마스킹을 이용해서 풀이한 문제입니다. 맨 처음에 각 친구가 알고 있는 문제를 비트로 표현한 후, 이를 배열(prob)에 담아주는데요. 예를 들어 1번 친구가 3, 4, 5번 문제를 알고 있다면 0b11100(2) = 4+8+12 = 24 라는 숫자가 배열의 1번 인덱스에 들어가게 됩니다. 그러면 결과적으로 각 배열의 값은 해당 친구가 풀 수 ..
