All
KMP(Knuth-Morris-Pratt)은 무엇인가? KMP는 대표적인 문자열 매칭 알고리즘으로, 문자열과 패턴이 주어질 때 문자열 안에서 주어진 패턴을 찾아내는 알고리즘이다. 만약, 길이가 1,000,000인 문자열과 길이가 10,000인 패턴이 주어졌을 때 단순하게 모든 문자열의 경우의 수를 확인한다면 시간 복잡도는 1,000,000 * 10,000이 될 것이다. 즉, O(N^2)이 된다. 그러나 KMP 알고리즘을 사용한다면 사실상 O(N)으로 시간 복잡도를 줄일 수 있다. 이렇게 시간 복잡도를 줄일 수 있는 이유는 접두사, 접미사를 이용하여 불필요하게 반복되는 연산을 줄이기 때문이다. 접두사, 접미사 최대 개수를 담은 table 생성 앞서 말한 과정에서 미리 계산해 둔 접두사, 접미사 정보를 활용..
웹 서버란? 웹 서비스는 서비스를 제공하는 서버 부분과 이를 이용하는 클라이언트로 구성이 된다. 사용자들이 이용하는 웹 브라우저가 대표적인 클라이언트 중 하나이다. 이에 반해 클라이언트에게 서비스를 제공하는 서버 프로그램을 웹 서버라고한다. 다시말해 클라이언트가 서버에게 특정 리소스를 요청하면 웹 서버는 요청에 따른 리소스를 반환해주게 된다. 대표적인 웹 서버 프로그램으로는 Apache, Nginx, IIS등이 있다. Apache란? 웹 서버 프로그램 중 하나로 아파치 소프트웨어 재단에서 제공하는 대표적인 오픈소스 HTTP 서버이다. Apache는 자체적으로 다양한 기능을 제공하지만, 다양한 종류의 서드파티 모듈 설치를 통해 여러 기능들을 사용자 환경에 맞게 언제든지 추가와 삭제가 가능하고, 그 업데이트..
현재 hostname 확인 [root@localhost /]# hostname hostname localhost.localdomain 초기 hostname은 localhost인 것을 확인할 수 있다. hostname 변경 # 일시적 변경 ( 재부팅 시 원상복구 ) [root@localhost /]# hostname server [root@localhost /]# hostname server [root@localhost /]# reboot [root@localhost ~]# hostname localhost.localdomain ----------------------------- # 영구적 변경 [root@localhost ~]# hostnamectl set-hostname server [root@loc..
virtual box로 CentOS를 설치하고 호스트 전용 네트워크를 설정해주었는데도 yum install도 안되는 상황이 발생할 수 있다. 이는 인터페이스가 활성화가 안되어있을 가능성이 있다. 이번에는 이러한 문제를 해결할 수 있는 방법인 네트쿼크 인터페이스를 활성화하는 방법에 대하여 써보고자 한다. 네트워크 인터페이스 확인하기 $ ip addr 1: lo: mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000 link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00 inet 127.0.0.1/8 scope host lo valid_lft forever preferred_lft forever inet6 ::..
문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1..
문제 두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다. A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다. 삽입: A의 한 위치에 문자 하나를 삽입한다. 삭제: A의 문자 하나를 삭제한다. 교체: A의 문자 하나를 다른 문자로 교체한다. 두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 최소 편집 횟수를 출력한다. 예제 입력 1 abc ab예제 출력 1 1예제 입력 2 ca abc예제 출력 2 3 나의 풀이 해당 문제는 두 문자열의 편집 거리(edit dis..
문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 의 경우에서 위로 블록을 이동시키면 의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 의 상태가 된다. 의 상태에서 블록을 오른쪽으로 이동시키면 가 되고, 여기서 다시 위로 블록을 이동시키면 이 된다. 여기서 오른쪽으로 블록을..
문제 링크 나의 풀이 우선 문제를 푸는 방법을 크게 정리하면 다음 과정을 거친다. 주어지는 블럭을 내려보낸다. 행(green) 또는 열(blue)가 꽉 찬 곳이 있는지 확인 있다면 해당 행 또는 열을 비워준다. 아래 빈 공간이 있는 블럭들을 아래로 내려보낸다. 2번의 과정을 반복한다. 연한 색의 칸에 블럭이 존재하는지 확인 존재한다면 해당 개수만큼 pop -> append [주의해야할 점] 큰 흐름으로 보면 그다지 어려워보이지 않지만 까다로운 조건들이 몇가지 있었다. 첫번째로 가로로 된 블록의 경우 붙어있어야 된다는 것이다. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -> 0 0 0 0 2 2 0 0 -> 2 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0..
문제 Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is not checked with the reported opponent. So, it is possible for competitors to make up matches and falsely report themselves as the winners. ..
