SW정글 7기 4주차: 알고리즘 끝, Red-Black Tree 시작

목차

3주차 알고리즘 시험 후기

Red-Black Tree 구현중

3주차 알고리즘 시험

하 문제

간단하게는 파이썬 데코레이터 @cache를 재귀함수에 붙이면 되고, DP 배열을 사용해서 호출 인자가 같은 경우에 DP배열에서 꺼내서 쓰면 된다.

 

중 문제

n*n격자에 숫자가 적혀 있고, 1행 1열에서 시작해서 n행n열까지 가야한다.

 

규칙은 현재 위치에 적힌 숫자보다 작은 칸만 갈 수 있다. 이때, n*n에 도달 가능한 경로의 개수를 구하는 문제다. DP를 사용하지 않고 DFS코드를 작성한다면 시간초과가 난다. 한 격자에서 4방향에 대해 DFS를 호출하고, 각각의 4방향에 대해 다시 4방향의 DFS를 호출하기 때문에 N*N이라면 시간복잡도가 O(4^(N*N))이다. 그래서 DP를 적용해야 한다.

 

문제에서 (N,N)에 도달하려면 이전칸은 (N-1,N)이거나 (N,N-1)이어야 한다. 이때, 우선 이전 칸에 적힌 숫자가 (N,N)에 적힌 숫자보다 커야 한다는 조건을 만족해야 하는 칸에서만 (N,N)에 접근할 수 있다.

 

(N-1, N), (N, N-1)에 접근하려면 마찬가지로 해당 칸의 주변에서 접근해야 한다.

DP[i][j]: (i, j)에 도달할 수 있는 경로의 개수. 그래서 4방향의 DP값을 더한 값을 DP[i][j]에 넣고 리턴하면 된다.

시험 이후 본 적이 없어서 아직 이해를 완전히 못했다. 다시 봐야겠다.

 

상 문제

강의들의 시작시간과 종료시간이 주어질 때, 모든 강의를 수업하는 경우에 최소 필요한 강의실의 개수와 강의별로 배정된 강의실의 번호를 출력하는 문제다.

 

시작시간이 이른 순서대로 강의를 진행해야 한다. 그래서 일단 강의를 시작시간 기준 오름차순 정렬하고, 순회를 한다.

그리고 강의실과 강의를 매치해서 어딘가에 넣는다. 이게 들어가는 곳은 최소힙이고, 해당 강의실의 강의가 끝나는 시간을 기준으로 오름차순 정렬되어 있어서, pop된 강의의 끝나는 시간이 다시 그 강의실을 사용할 수 있는 시간이 된다.

 

그래서 우선 강의실이 없을 때는 그냥 힙에 넣고, 이후 강의를 순회하면서 최소힙에서 뽑아낸 강의실이 아직 사용중이면 새 강의실을 만들어 넣고, 사용할 수 있으면 끝나는 시간을 갱신해서 넣는 방식으로 풀면 된다. 

 

Red-Black Tree 구현중

공부 순서

c언어 공부 -> 레드블랙트리 이론 -> 단일 연결리스트 구현 -> 이중 연결리스트 구현 -> 이진탐색트리 구현 -> 레드블랙트리 구현

 

이진탐색트리 구현 및 정석코드 공부를 마치고 레드블랙트리 구현에 들어갔다.

레드블랙트리 이론공부를 통해 트리의 균형을 이루게 하는 5가지 조건들이 있다는 걸 알았고, 삽입과 삭제시 여러 조건을 불만족하는 케이스에 대해 각각 어떻게 해야 모든 조건을 만족시킬 수 있는지 배웠다. 지금부터는 내가 배운걸 코드로 작성할 수 있느냐의 시간이다.

 

이론 -> 필요한 구조체, 함수 파악 -> 단계별 주석 -> 코드화

 

목표: 월요일에 삽입, 삭제 구현 완료

(현재: 9/5 화 삽입 - HJL's 힌트로 해결, 삭제 - 수도코드 참고해서 구현 완료 및 테스트케이스 all pass)

 

삽입할곳 찾아서 넣는건 while로 돌리면 되고, 노드 넣은 후에 조건 불만족하는지 확인하고, 어떤 케이스에 속하는지 파악 후 해결하기. 재귀호출이 필요한 경우도 있으니까 유의.

 

삭제는 일단 삭제할 노드 찾는거부터 시작. 같은 키 여러개면 가장 위에있는걸 삭제. 해당 노드의 색이 빨간색이면 그냥 지우고 연결하고, 검은색이면 extra black 생기고, 이게 붙을 노드를 찾아서 붙였을 때, red-and-black이면 그냥 블랙으로 칠하고, doubly black인 경우에 만 고려해주면 된다.