[2024년 3월] 알고리즘 풀이가 쌓이면 뭐든 된다(?)

[ParkJungYoon]

✅ TO DO

• 문자열
  • [x] 2941: 크로아티아 알파벳
• 정렬, 힙
  • [x] 2075: N번째 큰 수
• 자료구조
  • [x] 11478: 서로 다른 부분 문자열의 개수
• 탐색
  • [x] 1520: 내리막 길
• 그리디
  • [x] 1783: 병든 나이트
• 분할 정복
  • [ ] 1074: Z

---

복습

• [ ] 2075: N번째 큰 수
• [ ] 1520: 내리막 길
• [ ] 5525: IOIOI
• [ ] 1783: 병든 나이트

[ParkJungYoon]

03.03(일): N번째 큰 수

• 힙을 활용하는 아이디어!
• N번째 큰 수니깐 값을 일단 넣고
• 최소힙으로 작은 수 꺼내서 그것보다 크면 큐에 넣고 아니면 빼기

[ParkJungYoon]

03.04(월): 서로 다른 부분 문자열의 개수

• 중복 없이 저장하는 자료구조 set을 알면 쉽게 풀리는 문제

[ParkJungYoon]

03.04(월): 내리막 길

와.. 이해가 잘 안되는데 ㅠ_ㅠ

그냥 dfs만 쓰면 시간초과 난다.
dfs + dp 사용해야할거 같다.
https://simsimjae.tistory.com/20
- dfs는 50*50 2차원 배열에서도 시간초과 확률이 높다.
- 그래서 최대한 중복 연산을 피해야 한다. (dp를 활용해서)
- (0,0)에서 (4,4)를 거쳐 (50,50)으로 가는 경로가 있다면 (4,4)까지 가는 경로의 수를 미리 계산해둔다면 중복 계산을 피할 수 있다.

- 방문한 적이 없다면 계속 타고가서 최종 목적지에 도착하면 +1 해서 현재 노드에서 몇개의 코스로 목적지까지 가는지 누적해둠

[ParkJungYoon]

05.02(목) : 크로아티아 알파벳

[ParkJungYoon]

05.02(목) : 병든 나이트