Algorithm
[백준(Python/Java)] 9251_LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분수열 문제는 DP를 이용해 풀 수 있는 대표적인 문제입니다. 이 문제를 DP를 이용하지 않고 완전탐색으로 풀었을 때에는 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해서 비교해봐야 합니다. 그러면 문자열 s1의 모든 가능한 부분수열을 구할 때 2^(s1의 길이) 만큼의 시간이 소요되고, 이를 s2의 문자열과 비교해봐야 하기 때문에..
CS/OS
[운영체제/OS] 시스템 콜(System Call)에 대한 간단한 정리
1. 시스템 콜(System calls) 운영체제에 대한 첫 포스팅부터 계속 System Call에 대한 인터럽트를 이야기했는데요. 그래서 지금 대표적인 System Call에는 어떤 것들이 있는지 잠깐 짚어보려고 합니다. 1. fork() fork()는 새로운 프로세스를 생성하고, 프로세스 생성 요청을 보낸 프로세스(Calling Process)를 복제하는 시스템 콜입니다. 여기서 복제되는 프로세스를 Child, fork()를 수행하는 프로세스를 Parent라고 하는데요. fork()를 수행하게 되면 기본적으로 pid를 제외한 모든 내용이 동일하게 Child 프로세스에 복사됩니다. 또한, fork() 명령어 수행 시 Parent는 Child의 pid값을 리턴하고, child는 0을 리턴합니다. 그래서 ..
Algorithm
[백준(Python/Java)] 5052_전화번호 목록
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 이 문제를 푸는 방법은 크게 두 가지가 있습니다. 첫번째는 Trie 자료구조를 이용해서 문자열 탐색을 하는 방법이고, 두번째는 제가 푼 방법처럼 정렬을 이용해 탐색을 하는 방법입니다. 조금 더 일반적인 풀이 방법은 Trie 자료구조를 이용하는 것이겠지만 이 문제는 하나의 전화번호가 다른 전화번호의 Prefix가 되는지 여부만 판별해주면 되기 때문에 정렬을 이용할 수 있다고 ..
Algorithm
[백준(Python/Java)] 2143_두 배열의 합
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 이 문제에서 구하고자 하는 내용은 아래와 같습니다. 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A..
Algorithm
[백준(자바/Java)] 6087_레이저 통신(BFS, 우선순위 큐)
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS와 우선순위 큐를 사용하여 풀 수 있는 문제입니다. 카카오 2020 인턴십 "경주로 건설"과 비슷한 느낌의 문제라고 생각해서, 혹시 풀어보시지 않은 분이 계시면 풀어보면 좋을 것 같습니다. 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],..
Algorithm
[백준(Python/Java)] 11725_트리의 부모찾기(DFS, BFS)
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 연결 정보가 주어졌을 때, 각 노드의 부모 노드가 몇 번 노드인지를 묻는 문제입니다. 문제 조건에서 루트 노드가 항상 1번이라는 조건이 있으므로 1번 노드부터 DFS나 BFS 탐색을 시작합니다. 현재 노드를 A라고 하고 그 다음에 탐색을 할 노드를 B라고 한다면, B노드의 부모는 A가 되므로 한 번의 DFS 혹은 BFS 수행으로 모든 노드의 부모 노드를 정할 수 있습니다. 저 같은 경우에는 BFS를 이용해서 문제를 해결했습니다. [풀이 - 파이썬] fr..
Algorithm
[백준(Python/Java)] 4386_별자리 만들기 - 최소 신장 트리
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 이용하는 기본적인 문제로 저는 우선순위 큐를 이용해 해결했습니다. MST는 모든 정점을 연결하는 최소 비용의 간선들의 집합을 구해야 하므로, 임의의 정점 하나를 잡고 시작합니다. 이 임의의 정점도 반드시 언젠가는 포함되어야 하기 때문이죠. 그리고 해당 정점에서 연결된 간선들 중에서 최소 비용인 간선을 뽑고, 해당 간선과 이어진 정점이 방문하..
Spring & Springboot
[스프링/Spring] @Controller 그리고 @RestController
📖 문제 오늘은 프로젝트에서 어떤 아이템들을 분류하기 위한 카테고리를 생성하는 코드를 짜다가 마주한 문제에 대해 글을 작성해보려고 합니다. 사실 이 글을 작성한 지 한 달이 좀 넘어서 부분적인 내용을 수정하고 있는데 @Controller와 @RestController의 차이는 정말 당연한 개념이지만 반드시 알아야 하는 개념인 것 같습니다. 아래 코드를 보면서 이야기해보겠습니다. @Controller @RequiredArgsConstructor public class CategoryApiController { private final CategoryService categoryService; // 등록 API @PostMapping("/api/category/add") public Integer save(..
CS/Database
[데이터베이스/DB] 정규화에 대해서(2) - 제1,2,3 정규형과 BCNF
0. 들어가면서 이전 시간에 정규화는 함수적 종속성과 밀접한 관련이 있다고 했습니다. [데이터베이스/DB] 정규화에 대해서(1) - 이상(Anomaly)과 함수적 종속성(FD) 0. 오버뷰(Overview) 관계형 데이터베이스에서 설계 시 중복을 최소화하기 위해 데이터를 구조화하는 작업을 정규화(Normalization)라고 합니다. 정규화가 왜 필요한지에 대해 이야기하기 위해서, 아래 studyandwrite.tistory.com 릴레이션에는 여러 가지 속성들이 들어가있고, 정규화라는 것은 함수적 종속성을 이용해서 릴레이션을 연관성있게 구성하고 이상(Anomaly)을 없애는 과정이었죠. 정규화에는 크게 제1, 제2, 제3, BCNF 정규형이 있습니다. 각 정규형은 그 단계가 커질수록 그 이전 단계의 정..
Algorithm
[백준(Python/Java)] 1987_알파벳 - DFS
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(DFS)을 통해 가장 긴 알파벳을 찾는 문제였습니다. 기존에 풀었던 많은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)를 문제에서는 방문한 곳을 true로 체크하여 재방문을 하지 않도록 알고리즘을 설계했습니다. 하지만 이 문제에서는 깊이 우선 탐색을 하여 방문한 곳들이 최적해가 되지 않을 때, 다시 그 곳들의 방문 여부를 false로 복원하여 다음 탐색에서 방문할 수 ..
