취업을 위해 코딩 테스트는 필수적인 요소이며, 알고리즘 문제를 효과적으로 해결하는 능력은 면접관에게 좋은 인상을 남길 수 있습니다. 이번 강좌에서는 ‘DNA 비밀번호’라는 주제로 문제를 살펴보고, 해결 과정을 단계별로 설명하겠습니다. DNA 비밀번호는 알고리즘 문제에서 종종 등장하는 패턴 인식, 문자열 처리 및 최적화의 개념을 포함합니다.
문제 설명
DNA 비밀번호는 특정 DNA 시퀀스에서 주어진 길이를 갖는 비밀번호가 얼마만큼 존재하는지를 찾는 문제입니다. DNA 문자열은 ‘A’, ‘C’, ‘G’, ‘T’ 네 가지 문자로 구성됩니다. 우리는 주어진 DNA 시퀀스와 비밀번호의 길이를 입력으로 받아, 이 비밀번호가 몇 번 나타나는지를 출력해야 합니다.
문제 정의
문제: DNA 비밀번호
입력:
1. DNA 시퀀스 (문자열)
2. 비밀번호 길이 (정수)
출력:
주어진 비밀번호 길이를 가진 모든 문자열이 시퀀스 내에 몇 번 나타나는지 출력하라.
문제 해결 과정
1단계: 문제 이해하기
주어진 입력을 바탕으로 DNA 문자열 내부에서 가능한 모든 길이의 비밀번호를 추출하여 그 빈도를 세는 것을 목표로 합니다. 이 문제는 슬라이딩 윈도우 기법과 해시 맵을 활용해 최적화할 수 있습니다.
2단계: 슬라이딩 윈도우 이해하기
슬라이딩 윈도우는 연속된 부분 배열(또는 부분 문자열)을 다루는 데 유용한 기술입니다. 고정된 크기의 창(window)을 사용하여 문자열 내에서 비밀번호를 검색하려면, 현재 창의 위치를 지속적으로 이동시키면서 새 값을 추가하고 오래된 값을 제거해 현재의 상태를 유지합니다. 이를 통해 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.
3단계: 해시 맵 활용하기
해시 맵을 사용하여 비밀번호의 빈도를 세고 업데이트할 수 있습니다. 이 구조는 각 비밀번호가 출현할 때 그 빈도를 빠르게 확인하고 수정하는 데에 유리합니다.
4단계: 구현하기
이제 실제 C# 코드를 작성해 보겠습니다. 아래 코드는 주어진 입력에 대해 DNA 비밀번호의 출현 빈도를 계산합니다.
using System;
using System.Collections.Generic;
public class DnaPassword
{
public static int CountDnAPasswordOccurrences(string dna, int passwordLength)
{
if (dna.Length < passwordLength || passwordLength <= 0)
return 0;
Dictionary passwordCount = new Dictionary();
// 슬라이딩 윈도우를 위한 초기화
for (int i = 0; i <= dna.Length - passwordLength; i++)
{
string password = dna.Substring(i, passwordLength);
if (passwordCount.ContainsKey(password))
{
passwordCount[password]++;
}
else
{
passwordCount[password] = 1;
}
}
// 결과 출력
foreach (var entry in passwordCount)
{
Console.WriteLine($"Password: {entry.Key}, Count: {entry.Value}");
}
return passwordCount.Count; // 고유 비밀번호의 수 반환
}
public static void Main(string[] args)
{
Console.WriteLine("DNA 비밀번호 프로그램");
string dnaSequence = "ACGTACGTAGCTAGCTAGCTAGC"; // 예시 DNA 시퀀스
int passwordLength = 3; // 비밀번호 길이
int uniqueCount = CountDnAPasswordOccurrences(dnaSequence, passwordLength);
Console.WriteLine($"고유 비밀번호의 수: {uniqueCount}");
}
}
5단계: 코드 설명
위 코드는 주어진 DNA 문자열 내에서 주어진 길이의 비밀번호를 찾아 그 빈도를 센 후 결과를 출력합니다.
- 주어진 DNA 문자열과 비밀번호 길이를 확인한 후, 길이가 부족하거나 비밀번호 길이가 0 이하일 경우 0을 반환합니다.
- 슬라이딩 윈도우를 사용하여 DNA 문자열에서 비밀번호를 생성하고 해시 맵에 빈도를 저장합니다.
- 마지막으로 모든 비밀번호와 그 빈도를 콘솔에 출력하고, 고유 비밀번호의 수를 반환합니다.
결론
DNA 비밀번호 문제는 문자열 처리 및 해시 맵을 통해 효과적으로 해결할 수 있습니다. 알고리즘 문제를 해결할 때는 문제를 이해하고 효과적인 자료구조와 알고리즘을 사용하여 최적화하는 것이 중요합니다. 본 강좌에서 다룬 내용이 C# 코딩 테스트 준비에 도움이 되기를 바랍니다.