제민
4월 1주차 정리노트 본문
피곤한 4월입니다... 이번주엔 다양하게 학습했습니다.
위상정렬을 배우고 한 문제 해결하긴 했는데 정리에선 제외하려고 합니다.
BFS / DFS
https://jemin06.tistory.com/140
11967 불켜기
오래전에 풀다가 막혔던 문제인데 그래프/트리를 땐 김에 풀어보기로 했다. 인접리스트/인접행렬 등 그래프를 나타내는 방법들을 배우고 나니 BFS를 틀에 얽메이지 않고 좀 더 자유롭게 쓸 수 있
jemin06.tistory.com
BFS 문제집에서 처음 보고 그래프를 배운 뒤에 풀려고 남겨놓은 문제입니다. 배우고 나니 사고 폭이 넓어져 풀 수 있게 되었습니다. Vis 배열로 도달할 수 있는 곳인지 판단하는 부분이 인상깊었다.
https://jemin06.tistory.com/141
20304 비밀번호 제작
https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그
jemin06.tistory.com
이것도 BFS 문제집에서 남겨놨던 문제인데, 안전거리를 1 증가시키는 비트 연산자를 발견하는게 중요한 문제였다. 나머진 간단했는데, XOR 연산의 응용이 어려웠다.
https://jemin06.tistory.com/148
16724 피리 부는 사나이
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의
jemin06.tistory.com
현재 단계에서 DFS를 하다가 cycle이 형성되면 ans++을, 이전 단계에서 탐색한 노드를 만나면 return;을 해주면 되는 간단한 문제인데, -> <- 형태의 보드 처리에서 햇갈린 문제. ->에서 시작한다고 한다면 오른쪽으로 갔다가 다시 왼쪽으로 갈 때 이미 간 곳이므로 사이클이 형성됩니다. 이 점만 주의하면 문제를 쉽게 해결할 수 있습니다.
분할 정복
https://jemin06.tistory.com/142
2263 트리의 순회
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주
jemin06.tistory.com
도저히 못풀겠어서 답을 본 문제입니다. 간만에 본 분할 정복 문제인데, 재밌었습니다.
https://jemin06.tistory.com/146
4256 트리
https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까
jemin06.tistory.com
2263 트리의 순회를 풀고 자신감이 생겨서 혼자 풀어본 문제입니다.
https://jemin06.tistory.com/144
5639 이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수
jemin06.tistory.com
다시 글을 보니 잘못된 부분이 보인다. 이진 검색 트리를 Set으로 생각하고 보면 같은 값이 들어온다면 DFS 코드도 옳은 동작을 한다.
Dynamic Programming
https://jemin06.tistory.com/143
LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYK
jemin06.tistory.com
최장 부분 공통 ㅁㅁ 는 항상 어려웠는데 LCS도 마찬가지였다. 이런 웰노운 DP는 한 번에 이해가 안되면 암기를 해야 하는 것 같다. 규칙을 찾고 나니 나머지 문제는 풀 수 있었다.
https://jemin06.tistory.com/145
2342 Dance Dance Revolution
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자
jemin06.tistory.com
탑다운 DP로 해결하는 문제이다. 골드 DP는 항상 어렵다.
https://jemin06.tistory.com/147
17404 RGB거리 2
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩
jemin06.tistory.com
RGB거리와 같은데, 첫 번째와 마지막 집 색이 달라야 한다. 그냥 무식하게 for문을 써서 모든 경우의 수를 보면 해결할 수 있다.
기타
https://jemin06.tistory.com/149
2166 다각형의 면적
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는
jemin06.tistory.com
기하학 문제였습니다. 다각형의 넓이를 구하는데 사용되는 신발끈 공식에 대해 학습했습니다.
https://jemin06.tistory.com/153
1539 이진 검색 트리, 2957 이진 탐색 트리
https://www.acmicpc.net/problem/1539 1539번: 이진 검색 트리 P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트
jemin06.tistory.com
Set을 사용하는 문제였습니다. 굳이 Map을 이용할 필요는 없다고 느껴서 Set으로만 문제를 해결했습니다.
수행평가가 없어 수월한 한 주였습니다. 빨리 동아리 활동 하면서 같이 문제풀고싶은데 학교 일정이 방해하네요...
원래 바킹독 트리까지만 하고 마무리하려고 했는데 위상정렬을 들어보니 생각보다 재밌어서 완강하려고 합니다. 다 배우고 세그먼트 트리까지 배우면 플 3은 될거같네요.
'주별 개인평가' 카테고리의 다른 글
| 4월 2주차 정리노트 (0) | 2024.04.13 |
|---|---|
| 3월 3,4주차 정리노트 (0) | 2024.03.31 |
| 3월 2주차 정리노트 (0) | 2024.03.17 |
| 3월 1주차 정리노트 (0) | 2024.03.09 |
