99클럽 코테 스터디 11일차 TIL + 오늘의 학습 키워드 해시

- 오늘의 학습 키워드 슬라이딩윈도우, 해시
- 공부한 내용 본인의 언어로 정리하기

dna 에서 반복된 10글자의 시퀀스 찾기 문제

 

알고리즘 접근법: 해시 테이블, set 자료구조를 활용하는 슬라이딩 윈도우 알고리즘을 사용한다.

 

문제 접근 방법: 

문자열을 처음부터 끝까지 스캔하여 길이가 10인 모든 문자열을 추출한다.

각 부분 문자열이 이전에 나온건지 체크, 결과 집합에 추가하낟.

중복된 시퀀스만 반환한다.

 

function findRepeatedDNASequences(s);
	if length(s) <10; 
    	return empty array
        
        seen = empty hash set
        result = empty hash set
        
        for i from 0 to length(s) -10;
        	substring = s[i:i+10]
            
            if substring exists in seen;
            add substring to result
            
            else:
            	add substring to seen
                
          return result as array

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

인덱스 범위에 벗어나서 에러났음

 

  - 어떻게 해결했는지

슬라이딩 윈도우의 개념을 제대로 이해하지 못해서 s.length() -10을 왜 해야하는지 몰랐음

문제에서 10개를 무조건 지켜야한다고 햇으므로 전체 인덱스 범위를 벗어나지 않게 하지위해서 s.length()-10을 해준다.

  - 무엇을 새롭게 알았는지

슬라이딩 윈도우: 고정된 크기의 창(window)를 데이터 위에 이동하면서 연속된 데이터를 처리하는 알고리즘이다.

매번 반복될때마다 창은 한위치씩 오른쪽으로 이동하는데 그때 해당창에 10글자를 추출하고 처리하는데 이를 

 

for (int i = 0; i <= s.length() - 10; i++) {
    String substring = s.substring(i, i + 10);
    
}

 

이런 코드로 만들수가 있다.
  - 내일 학습할 것은 무엇인지