CS/Algorithm
[백준(Python/Java)] 14890_경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 해석을 잘못해서 엄청나게 복잡한 코드를 생각했었는데요. 처음에 이 문제를 봤을 때는 "가로로 설치한 경사로와 세로로 설치한 경사로가 겹치면 어떻게 하지?"에 대한 처리를 엄청 고민했습니다. 하지만 이 문제는 가로와 세로에 설치한 경사로를 따로 구분해서 푸는 문제이기 때문에 위와 같은 상황은 고려하지 않아도 되는 것이었죠. 따라서 이 문제는 매우 간단해집니다. 주어진 이차원 배열의 모든 행과 열을 탐색해보면서 해당..
CS/OS
[운영체제/OS] 동기화 이슈 처리하기 - (2)
💡 1. High-level Synchronization ? 예전 포스팅에서 Software-only solution(피터슨 알고리즘)과 Hardware Atomic solution(Test-and-Set, Swap)으로 동기화 이슈를 처리하는 방법에 대해 공부해봤는데요. * 해당 부분에 대한 포스팅이 궁금하신 분은 아래 링크에서 확인해주세요. [운영체제/OS] 동기화 이슈 처리하기 - (1) 0. 문제 상황 // Producer = 데이터를 추가하는 역할(counter 증가) register A := counter; // load register A := registerA + 1; // add counter := registerA; // store // Consumer = 데이터를 빼는(소모하는.. s..
CS/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을 리턴합니다. 그래서 ..
CS/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가 되는지 여부만 판별해주면 되기 때문에 정렬을 이용할 수 있다고 ..
CS/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..
CS/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],..
CS/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..
CS/Algorithm
[백준(Python/Java)] 4386_별자리 만들기 - 최소 신장 트리
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 이용하는 기본적인 문제로 저는 우선순위 큐를 이용해 해결했습니다. MST는 모든 정점을 연결하는 최소 비용의 간선들의 집합을 구해야 하므로, 임의의 정점 하나를 잡고 시작합니다. 이 임의의 정점도 반드시 언젠가는 포함되어야 하기 때문이죠. 그리고 해당 정점에서 연결된 간선들 중에서 최소 비용인 간선을 뽑고, 해당 간선과 이어진 정점이 방문하..
CS/Database
[데이터베이스/DB] 정규화에 대해서(2) - 제1,2,3 정규형과 BCNF
0. 들어가면서 이전 시간에 정규화는 함수적 종속성과 밀접한 관련이 있다고 했습니다. [데이터베이스/DB] 정규화에 대해서(1) - 이상(Anomaly)과 함수적 종속성(FD) 0. 오버뷰(Overview) 관계형 데이터베이스에서 설계 시 중복을 최소화하기 위해 데이터를 구조화하는 작업을 정규화(Normalization)라고 합니다. 정규화가 왜 필요한지에 대해 이야기하기 위해서, 아래 studyandwrite.tistory.com 릴레이션에는 여러 가지 속성들이 들어가있고, 정규화라는 것은 함수적 종속성을 이용해서 릴레이션을 연관성있게 구성하고 이상(Anomaly)을 없애는 과정이었죠. 정규화에는 크게 제1, 제2, 제3, BCNF 정규형이 있습니다. 각 정규형은 그 단계가 커질수록 그 이전 단계의 정..
