문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 이 문제는 단순히 BFS, DFS를 사용하면 해결하기 매우 힘들다. 모든 자리에서 4방향을 모두 조사하는 식으로 탐색하면 경우의 수가 너무 많아 시간 초과가 발생한다. 따라서 조합을 사용하여 해결하는 편이 좋다. 25개의 자리 중 7개를 선택하는 경우의 수는 25C7 = 480700 으로 작은 편이다. 1. 25개의 자리 중 7개를 뽑는다. 2. 해당 7개의 자리가 모두 상하좌우로 연결되어..
블로그 이사했습니다아래에서 해당 글을 보실 수 있습니다. https://code-lab1.com/b-tree/ [자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정 - 코드 연보통 B트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.code-lab1.com B- 트리란?보통 B 트리라고 하면 B- 트리를 의미한다. B 트리는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 이러한 B 트리의 다음과 같은 특징을 그림과 함께 알아보자. 1. ..
문제 https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 풀이 이 문제는 아이디어가 매우 중요하다. 알고리즘 분류에 슬라이딩 윈도우로 표시되어 있는 것을 보고 힌트를 얻었다. a가 연속적이여야 한다는 말은 a가 a의 개수 만큼 연속적으로 위치해야 한다는 뜻이다. 예를 들어, "ababa" 라는 문자열이 있다면, a가 3개이므로 "aaabb", "baaab", "bbaaa".... 등 a가 3개 연속적으로 위치해야한다. 따라서, 인덱스 0 부터 끝까지 ..
문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 코드를 짜는 것보다 예외를 처리하는게 훨씬 어려웠던 문제였다. 우선 다음과 같은 Fireball 클래스를 만들었다. public static class Fireball{ int r;// 행 int c;// 열 int m;// 질량 int s;// 속력 int d;// 방향 Fireball(int r,int c,int m, int s,int d){ ..
얼마전에 유튜브에서 재밌는 C-code를 보게 되었다. https://youtu.be/DEqXNfs_HhY Donut-shaped C code 별로 쓸데는 없지만 재밌어 보여서 나도 구현해보고 싶어졌다. 하지만 구글에 Donut-shaped C code를 검색해봐도 제대로 된 코드를 찾기가 쉽지 않았다. 겨우 찾은 코드에서 몇가지 오류가 나는 것을 해결해서 완성한 코드는 다음과 같다. #include #include #include #include int main(){ int k; float A=0, B=0, i, j, z[1760]; char b[1760]; printf("\x1b[2J"); for(; ; ) { memset(b,32,1760); memset(z,0,7040); for(j=0; 6.28..
프록시(Proxy)란? 프록시는 두 호스트가 통신할 때 서로 직접 통신하지 않고 중간에서 대리로 통신을 하도록 도와주는 것을 프록시(Proxy)라고 한다. 이러한 중계 역할을 하는 서버를 프록시 서버라고 부른다. 즉, 프록시 서버는 클라이언트와 서버 사이의 중계서버로서의 역할을 한다. 이러한 프록시 서버가 클라이언트와 서버 중간에 위치하면서, 클라이언트는 프록시서버를 서버로 인식하고 서버는 프록시 서버를 클라이언트로 인식하게 된다. 프록시서버는 위치에 따라 포워드 프록시(Forward Proxy)와 리버스 프록시(Reverse Proxy)로 나뉜다. 포워드 프록시(Forward Proxy)란? 포워드 프록시는 일반적으로 프록시, 프록시 서버 혹은 웹 프록시라고 불린다. 포워드 프록시는 클라이언트들 앞에 ..
문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 이 문제는 간단한 BFS 문제이다. 다만 일반적인 BFS와 달리 방문 여부를 체크하지 않는다. 대신 6개의 숫자를 택하면 더 이상 탐색을 진행하면 안 되는 식으로 구현하면 된다. 나는 다음과 같은 Node 클래스를 만들어서 큐의 원소로 사용했다. public static class Node{ int x; int y; String str; Nod..
템플릿 엔진이란? 템플릿 엔진은 템플릿 양식과 특정 데이터 모델에 따른 입력 자료를 합성하여 결과 문서를 출력하는 소프트웨어 또는 소프트웨어 컴포넌트를 말한다. 특히, 웹 템플릿 엔진은 웹 문서가 출력되는 템플릿 엔진을 말한다. 즉, 웹 템플릿 엔진은 지정된 템플릿 양식과 데이터가 합쳐져서 HTML 문서를 출력하는 소프트웨어를 말한다. 이후 웹 템플릿 엔진을 템플릿 엔진으로 부르겠다. 서버 사이드 템플릿 엔진 vs 클라이언트 사이드 템플릿 엔진 서버 사이드 템플릿 엔진은 서버에서 DB 혹은 API에서 가져온 데이터를 미리 정의된 템플릿(Template)에 넣어 HTML 문서를 만들어 클라이언트에 전달해주는 역할을 한다. 즉, HTML 코드에서 고정적으로 사용되는 부분은 템플릿으로 만들어두고 동적으로 생성..
서블릿(Servlet)이란? 자바 서블릿(Java Servlet)은 웹페이지를 동적으로 생성하는 서버 측 프로그램 혹은 그 사양을 말하며, 흔히 "서블릿"이라 불린다. -위키피디아- 서블릿은 웹 서버의 성능을 향상하기 위해 사용되는 자바 클래스의 일종이다. 기존에 서버는 정적인 자료(HTML, 사진, 글 등)만을 주고받았다. 하지만 웹에 다양한 기능이 요구되면서 정적인 자료뿐만 아니라 사용자 요구에 맞춘 동적인 페이지들을 만들 필요가 생겼다. 이를 위해 만들어진 것이 바로 서블릿이다. 쉽게 말해 서블릿은 클라이언트의 요청에 맞춰 동적인 결과를 만들어 주는 자바 웹 프로그래밍 기술이라고 할 수 있다. 이러한 서블릿은 WAS(Web Application Server)의 서블릿 컨테이너 안에서 동작하게 된다...
커넥션 비용 WAS(Web Application Server)와 데이터베이스 사이의 연결에는 많은 비용이 든다. MySQL 8.0을 기준으로 INSERT 문을 수행할 때 필요한 비용의 비율은 다음과 같다. 괄호 안의 숫자가 비율을 의미한다. 1. Connecting (3) 2. Sending query to server (2) 3. Parsing query (2) 4. Inserting row (1) 5. Inserting index(1) 6. Closing (1) 즉, 서버가 DB에 연결하기 위한 Connecting 비용이 가장 큰 비율을 차지한다. 이처럼 Connection을 생성하는 작업은 비용이 많이 드는 작업이다. 이를 보완할 수 있는 방법이 바로 Connection Pool이다. 커넥션 풀(C..