오늘 한 일
- 알고리즘 문제 오답
- 알고리즘 문제 풀이(2110, 6549, 11866, 1654, 2740)
Review
오늘은 이전에 푼 문제 중 정리가 필요한 것을 오답하고, 새로운 문제를 풀이하였다.
P11053. 가장 긴 증가하는 부분 수열
완전 탐색, DP, 이진탐색 3가지 방식으로 모두 풀이했다. 이진탐색으로 했을 때 시간 차이가 크게 나서 신기했다. 문제를 풀다보니, 이진탐색은 특정한 값을 찾기보다는 범위를 좁혀가며 범인을 잡는 것처럼 탐색하는 것 같다.
P11053. 가장 긴 증가하는 부분 수열
문제: https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 문제, 줄여서 LIS(Logest Increasing Subsequence)라고도 한다. 크게 완전탐색, DP, 이진탐색 방식으로 풀이할 수 있다. 유사한 문제가 여럿
mywnajsldkf.tistory.com
P2805. 나무 자르기
당시에 아이디어를 쉽게 떠올려서, 쉽게 풀었다고 생각했는데 다시 보니 너~무 헷갈렸다.
다른 사람의 블로그를 보니 이것을 결정 문제로 바꿔서 풀라고 하셨다. 그러니까 생각을 최소한의 범위를 만족할 수 있다면 그것까지는 True라고 보고, 나머지는 False가 되어서 True에서 최적의 답을 찾는 것이다. 한번 답을 찾으면 거기서 멈추는 줄 알았는데 그것이 아니었다.
P2805. 나무 자르기
- 문제: https://www.acmicpc.net/problem/2805 설명 이 문제를 풀 때 계속 실수한 점은 M 미터의 나무를 잘랐다고 반복을 멈췄다는 것이다. 문제를 읽어보면 이때, **적어도 M미터**의 나무를 집에 가져가기
mywnajsldkf.tistory.com
P2493. 탑
봐도봐도 센스있는 아이디어이다. 자료형을 잘 사용하는 문제는 비슷한 문제를 풀면서 센스를 채울 필요가 있다.
P2493. 탑
문제: https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸
mywnajsldkf.tistory.com
P2110. 공유기 설치
문제를 잘 이해하고, 관점을 특정 거리에서 목표하는 공유기 개수만큼 설치할 수 있는가? 로 바라본다면 풀린다. 문제 풀 때 대상을 잘 정의해야겠다.
P2110. 공유기 설치
문제 링크: https://www.acmicpc.net/problem/2110 설명 이 문제는 어떤 풀이를 써야할지 잡히지 않아 어려움이 있었다. 일단 가장 인접한 두 공유기 사이의 거리를 최대로 라는 말이 이해가 가지 않았다.
mywnajsldkf.tistory.com
새로운 문제 풀이
P2110. 공유기 설치
문제를 잘 이해하고, 관점을 특정 거리에서 목표하는 공유기 개수만큼 설치할 수 있는가? 로 바라본다면 풀린다. 문제 풀 때 대상을 잘 정의해야겠다.
P6549: 히스토그램에서 가장 큰 직사각형
이 문제는 이분탐색과 스택 모두 풀 수 있다.
이분탐색 방법은 merge sort를 생각하자! 다 쪼개고 합칠 때, 1) 좌 2) 우 3) mid값 합친 것 포함 중 가장 큰 값이 답이다.
코드에 익숙해져야 한다.
P11866
자료형을 센스있게 쓰는 것은 어렵다.
P1654
나무자르기 관련 문제 풀이했다. T, F로 바꿔서 풀었더니 잘 풀렸다.
P2740
2차원 배열로 row, col을 접근하고, 해당 값을 채우기 위해 M만큼 반복한다.
기타
코치님의 짧은 말씀과 생각 정리! 알고리즘에 관하여...
이번 주차는 지난번보다 알고리즘 푸는데 시간도 많이 걸리고 어려웠다. 평소 이분탐색은 많이 공부하지 않은 것도 있고, 문제 난이도도 전반적으로 어려워졌기 때문이다.
시간이 걸리더라도 오답을 하려고 하는데 코치님께서도 일단 이론이 다 정리가 되었다면 그런식으로 오답을 하면서 케이스를 채워나가는 것도 괜찮다고 하셨다. 또 알고리즘과 언어 공부의 영역은 크게 다르다고 하셨다.
알고리즘 하다보면 언어 자체에 대한 호기심도 생기는데(언어를 쓰다보니!) 레이더망을 조금 줄이고, 공부해보고 싶은 것들은 나의 deque에 append하여 하나씩 popLeft() 해야겠다!
일단 코테 통과가 우선이다.
내일 할 일✍️
- 알고리즘 문제 풀이
- 알고리즘 오답
- 이론 공부(퀴즈 공부 위주로!)
