본문 바로가기

2023 상반기/바이오 컴퓨팅17

Review of Algorithms2 Selection Sort 선택 정렬(Selection Sort)은 간단한 정렬 알고리즘으로, 주어진 배열에서 최소값을 찾아서 정렬된 부분과 교환하는 방식을 이용합니다. 배열에서 최소값을 찾고 시작 위치와 교환하는 과정을 반복하여 전체 배열이 정렬됩니다. 선택 정렬 알고리즘의 동작 방식은 다음과 같습니다: 배열에서 최소값을 찾아 시작 위치와 교환합니다. 시작 위치를 한 칸씩 오른쪽으로 이동하면서 이전 과정을 반복합니다. 예시: 주어진 배열: [64, 34, 25, 12, 22, 11, 90] 첫 번째 반복에서 최소값은 11이며, 시작 위치인 64와 교환됩니다. 정렬된 배열: [11, 34, 25, 12, 22, 64, 90] 두 번째 반복에서 최소값은 12이며, 시작 위치인 34와 교환됩니다. 정렬된 배.. 2023. 3. 22.
Review of Algorithms 과제 2, 문자열 조작 - 역방향 보수 DNA 서열의 역방향 보체 서열을 반환하는 파이썬 코드를 작성하십시오. 예를 들어, "ACCTGG"의 역 보수 시퀀스는 "CCAGGT"입니다. 코드는 입력 파일을 명령줄 인수로 사용하고, 입력 파일에서 DNA 서열을 읽고, DNA 서열을 반전하고, DNA 서열의 모든 'A', 'T', 'C', 'G'를 각각 'T', 'A', 'G's, 'C'로 변환하고, 출력 파일에 역방향 보수 서열을 인쇄해야 합니다. 입력 파일이 한 줄의 주석으로 시작하고 두 번째 줄의 DNA 서열이 여러 줄이라고 가정합니다. 주의 LearnUs를 통해 파이썬 코드를 제출하십시오. 파일 이름을 "Assignment2.py"로 지정합니다. 메모 입력 시퀀스는 대/소문자를 구분하지 않습니다. 입력 .. 2023. 3. 21.
RE 연습, 백준(14405, https://www.acmicpc.net/problem/14405 14405번: 피카츄 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문 www.acmicpc.net import re import sys testStr = sys.stdin.readline() pattern = r'^(pi|ka|chu)*(pi|ka|chu)*(pi|ka|chu)*$' if re.match(pattern, testStr): print("YES") else: print("NO") https://www.acmicpc.net/problem/46.. 2023. 3. 13.
1. 정규 표현식 RE(Regular Expression) & 유한 오토마타 DFA(Finite Automata) 파이썬의 RE 모듈을 사용해서 한다. 1. 정규 표현식(RE) 의 정의와 예시 정규 표현식(regular expression)은 문자열을 검색하고 매칭하는 패턴(pattern)을 정의하기 위한 표현식입니다. 정규 표현식은 일반적으로 문자열 검색, 문자열 대체, 문자열 분할 등의 작업에 사용됩니다. (): 그룹화 ()를 사용하여 정규 표현식을 그룹화할 수 있습니다. 그룹화된 정규 표현식은 |, *, + 등의 메타 문자와 함께 사용할 수 있습니다. 그룹화된 정규 표현식은 매치 결과에서 그룹 번호를 갖게 되며, group() 메서드를 통해 그룹에 매칭된 문자열을 가져올 수 있습니다. 예시: import re # (python|java)는 "python" 또는 "java"와 매치됩니다. # 매칭된 문자열은 gr.. 2023. 3. 8.
KMP 알고리즘 KMP 알고리즘은 문자열 검색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 문자열에서 다른 문자열을 검색할 때, 매번 전체 문자열을 처음부터 끝까지 일일이 비교하지 않아도 되도록 하는 것이 목표입니다. 이를 위해서 KMP 알고리즘은 패턴 문자열을 미리 분석하여 LPS 배열을 계산하고, 이를 이용하여 문자열 검색을 수행합니다. 예를 들어, "ABABDABACDABABCABAB"이라는 문자열에서 "ABABCABAB"이라는 패턴을 검색하고자 한다고 가정해봅시다. 먼저 KMP 알고리즘은 패턴 문자열인 "ABABCABAB"을 분석하여 LPS 배열을 계산합니다. 이때, LPS 배열은 아래와 같이 계산됩니다. i = 0: A, LPS[0] = 0 i = 1: AB, LPS[1] = 0 i = 2: ABA, LPS[2.. 2023. 3. 8.