[크래프톤 정글] 15일

wnajsldkf·2023년 4월 17일
0

정글

목록 보기
9/14
post-thumbnail

오늘 한 일

  • 알고리즘 문제 오답
  • 알고리즘 문제 풀이(2110, 6549, 11866, 1654, 2740)

Review

오늘은 이전에 푼 문제 중 정리가 필요한 것을 오답하고, 새로운 문제를 풀이하였다.

P11053. 가장 긴 증가하는 부분 수열
완전 탐색, DP, 이진탐색 3가지 방식으로 모두 풀이했다. 이진탐색으로 했을 때 시간 차이가 크게 나서 신기했다. 문제를 풀다보니, 이진탐색은 특정한 값을 찾기보다는 범위를 좁혀가며 범인을 잡는 것처럼 탐색하는 것 같다.

P2805. 나무 자르기
당시에 아이디어를 쉽게 떠올려서, 쉽게 풀었다고 생각했는데 다시 보니 너~무 헷갈렸다.
다른 사람의 블로그를 보니 이것을 결정 문제로 바꿔서 풀라고 하셨다. 그러니까 생각을 최소한의 범위를 만족할 수 있다면 그것까지는 True라고 보고, 나머지는 False가 되어서 True에서 최적의 답을 찾는 것이다. 한번 답을 찾으면 거기서 멈추는 줄 알았는데 그것이 아니었다.

P2493. 탑
봐도봐도 센스있는 아이디어이다. 자료형을 잘 사용하는 문제는 비슷한 문제를 풀면서 센스를 채울 필요가 있다.

P2110. 공유기 설치
문제를 잘 이해하고, 관점을 특정 거리에서 목표하는 공유기 개수만큼 설치할 수 있는가? 로 바라본다면 풀린다. 문제 풀 때 대상을 잘 정의해야겠다.

새로운 문제 풀이

P2110. 공유기 설치

문제 풀이
문제를 잘 이해하고, 관점을 특정 거리에서 목표하는 공유기 개수만큼 설치할 수 있는가? 로 바라본다면 풀린다. 문제 풀 때 대상을 잘 정의해야겠다.

P6549: 히스토그램에서 가장 큰 직사각형

이 문제는 이분탐색과 스택 모두 풀 수 있다.
이분탐색 방법은 merge sort를 생각하자! 다 쪼개고 합칠 때, 1) 좌 2) 우 3) mid값 합친 것 포함 중 가장 큰 값이 답이다.
코드에 익숙해져야 한다.

P11866

자료형을 센스있게 쓰는 것은 어렵다.

P1654

나무자르기 관련 문제 풀이했다. T, F로 바꿔서 풀었더니 잘 풀렸다.

P2740

2차원 배열로 row, col을 접근하고, 해당 값을 채우기 위해 M만큼 반복한다.

기타

코치님의 짧은 말씀과 생각 정리! 알고리즘에 관하여...
이번 주차는 지난번보다 알고리즘 푸는데 시간도 많이 걸리고 어려웠다. 평소 이분탐색은 많이 공부하지 않은 것도 있고, 문제 난이도도 전반적으로 어려워졌기 때문이다.
시간이 걸리더라도 오답을 하려고 하는데 코치님께서도 일단 이론이 다 정리가 되었다면 그런식으로 오답을 하면서 케이스를 채워나가는 것도 괜찮다고 하셨다. 또 알고리즘과 언어 공부의 영역은 크게 다르다고 하셨다.
알고리즘 하다보면 언어 자체에 대한 호기심도 생기는데(언어를 쓰다보니!) 레이더망을 조금 줄이고, 공부해보고 싶은 것들은 나의 deque에 append하여 하나씩 popLeft() 해야겠다!

일단 코테 통과가 우선이다.

내일 할 일✍️

  • 알고리즘 문제 풀이
  • 알고리즘 오답
  • 이론 공부(퀴즈 공부 위주로!)
profile
https://mywnajsldkf.tistory.com -> 이사 중

0개의 댓글