모북의 코딩블로그

오늘은 Alignment algorithm 중 global alignment에 해당하는 Needleman-Wunsch algoritm(니들만 브니쉬) 에 대해 알아보겠다. alignment 알고리즘은 LCS (longest commen sequence) 알고리즘과 유사하다. LCS에 대해 궁금하면 아래 글을 참고하자. 2023.05.21 - [Computer Science/Data structure & Algorithm] - [Algorithm] LCS (Longest Common Sequence) [Algorithm] LCS (Longest Common Sequence) DP의 대표 문제 중 하나인 LCS에 대해 다루어 보겠다. Longest Common Substring 공통 부분 문자열을 찾으라고 ..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 원래 알고리즘 C++로 했는데 이번 학기 들어와서 교수님이 python으로 수업하신다는 이야기 들어서 python으로 주 언어를 바꾸었다. (+ 연구실도 python 위주고 AI도 python이라 그냥 바꾸는게 편해보였다. ) 그래서 이제부터는 python으로 풀이를 진행할 것이다. 사실 문제는 그 사이에 많이 풀었는데 귀찮아서 글을 하나도 안올렸다. ..

DP의 대표 문제 중 하나인 LCS에 대해 다루어 보겠다. Longest Common Substring 공통 부분 문자열을 찾으라고 했을 때 우리는 보통 longest common substring을 생각하곤 한다. 이는 오늘 알아볼 LCS와는 다른 개념이니 혼동해서는 안된다. Longest Common Substring은 말 그대로 공통으로 가지고 있는 substring 중 가장 긴 것을 구한다. 이 문제는 DP로 해결할 수 있으며 굉장히 간단하게 구현이 가능하다. 두 문자가 같다면 [j-1][i-1]의 값에 +1을 하는 방식으로 위의 표를 채워나가면 된다. Longest Common Subsequence 1. 기본 개념 그럼 Common Subsequence는 무엇일까? 부분 수열 중 가장 긴 것이라..

오늘은 Optimal Binary Search Tree ( 최적 이진 탐색 트리 ) 에 대해 정리해보았다. Binary Search Tree Binary Search Tree는 Binary Tree의 성질을 만족하면서 Ordered 되어 있는 상태이다. BST의 성질은 다음과 같다. 왼쪽 자식 노드는 부모 자식의 값보다 작다. 오른쪽 자식 노드는 부모 자식의 값보다 크다. BST는 탐색시간을 줄여준다는 것에서 굉장히 큰 의미가 있다. Optimal BST (최적 이진 탐색 트리) 1. 기본 개념 오늘 할 Optimal BST는 BST 중 평균 탐색 시간이 가장 작은 Tree를 의미한다. 여기서 '평균 탐색시간'이란 무엇일까? 이때까지 우리는 노드를 탐색할 확률이 같다고 가정하고 Tree를 만들었다. (r..

AND/OR Gates these gates are instantiated to build logic circuits truth tables assuming two inputs BUF/NOT Gates BUF/NOT gates have one scalar input, several scalar output buf : 입력을 그대로 출력해주는 장치 노이즈가 생겼을 때 버퍼를 통과하면 노이즈가 사라진다. 주목할 점은 z를 넣으면 x가 output으로 나온다. not : 입력을 반대로 출력해주는 장치 output이 2개 이상 있을 수 있다. not n1 (OUT1, OUT2, IN); Gates with an additional control signal on BUF/NOT gates are also avai..

Modules A module is a basic building block consisting of distinct parts. module name, port list, port declarations, optional parameters … SR Latch Example module SR_latch(Q, Qbar, R, Rbar); output Q, Qbar; input R, Rbar; nand n1(Q, Sbar, Qbar); nand n2(Qbar, Q, Rbar); endmodule List of Ports Ports(terminal) provide the interface by which a module can communictaion with its environment. ⇒ the env..

'윤성우의 열혈 TCP/IP 프로그래밍' 서적을 참고하여 정리하였습니다. 인터넷 주소 (Internet Address) 인터넷 상에서 컴퓨터를 구분하는 목적으로 사용되는 주소 IPv4 → 4바이트 주소체계 IPv6 → 16바이트 주소체계 네트워크 주소와 호스트 주소로 나뉜다. 네트워크 주소를 이용해서 네트워크를 찾고, 호스트 주소를 이용해서 호스트를 구분한다. 클래스 별 네트워크 주소와 호스트 주소의 경계 Port 번호 IP는 컴퓨터를 구분하는 용도로 사용되며, PORT번호는 소켓을 구분하는 용도로 사용된다. PORT번호는 16비트로 표현된다. 0~1023 포트는 이미 용도가 있으며, 포트번호는 0이상 65535이하이다. IPv4 기반의 주소 표현을 위한 구조체 struct sockaddr_in { sa..

'윤성우의 열혈 TCP/IP 소켓 프로그래밍' 책을 참고하여 정리하였습니다. 프로토콜 & 소켓 - 소켓 : 네트워크 연결 도구 - 프로토콜 : 컴퓨터 상호간의 데이터 송수신 필요한 통신규약 소켓을 생성할 때 기본적인 프로토콜을 지정해야한다. 프로토콜 체계 PF_INET : IPv4 프로토콜 체계 PF_INET6 : IPv6 프로토콜 체계 소켓의 타입 데이터 전송방식을 의미한다. 소켓이 생성될 때 소켓의 타입도 결정되어야한다. 1, SOCK_STREAM : 연결 지향형 소켓 ( TCP 소켓 ) 중간에 데이터 소멸되지 않으며 전송 순서대로 데이터가 수신된다. 데이터의 경계가 존재하지 않는다. 소켓 대 소켓의 연결은 반드시 1대 1의 구조이다. 2. SOCK_DGRAM : 비 연결지향형 소켓 ( UDP 소켓 ..

https://www.acmicpc.net/problem/2156] 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은..