Always awake

백준 일지 (~04/07) 본문

PS

백준 일지 (~04/07)

죠. 2024. 4. 7. 23:27

03/20

  • DP
    • https://boj.kr/2293 동전 1 (G5)
      • 이제 DP연습해야지..
      • 처음에는 DP[N][K]로 각 동전마다 돌면서 가지수를 구해줬다.
        • $DP_{ij} = \sum_{k=0} ^{j // i} DP_{i-1j-k*coin}$
      • 근데 메모리 초과가 나더라?!!
      • 생각해보니 어차피 i-1번째만 참고해서, 한줄로 가능하다!
      • 그리고 여러번 업데이트되는쪽은 자기의 j-coin번째만 참고하면 된다.
      • 따라서 $DP_i = DP_i-coin$을 $i*j$번 돌면 완료!
    • https://boj.kr/2294 동전 2 (G4)
      • 위 문제와 같은 상황이지만, 이번에는 그걸 만족하는 최소 동전수 구하기
      • 비슷한 방법으로 채우면 되지 않을까?
      • 음! 잘 된다. 거의 같은 아이디어네.
    • https://boj.kr/1890 점프 (S1)
      • 그냥 $i*j$ 순회하면서 세면 될거같은데?
      • 맞네. 근데 길의 개수가 꽤 커질 수 있으니 long long으로, 그대로 순회하면 마지막 DP[N-1][N-1]번째 칸에서 4배가 되므로 (오른쪽갈때 두배, 아래로 갈때 두배) 4로 나눠주거나 그 타이밍에 break문을 걸면 된다. 나는 오버플로우날까봐 쫄아서 탈출로..
    • https://boj.kr/1520 내리막길 (G3)
      • 아.. 문제 제대로읽기.. ㅠㅠ 보자마자 위에서 아래로 내려오는건 필수인지알고 음? $O(N^3)$ 풀이로 그냥 위에서부터 훑으면서 내려오면 되겠는데? 싶었는데 바로 틀렸다..
      • 그럼 음.. 이럴때야말로 탑다운 해야하나? 무조건 내려와야한다는 조건때문에 순환을 돌것같지도 않으니, 재귀 돌려보자!
      • 탑다운이 짜기 훨씬쉽네??;;; 앞으로 바텀업 말고 탑다운 먼저 생각돌려야겠다.
    • https://boj.kr/1965 상자넣기 (S2)
      • LIS네 이거
      • 근데 LIS 구현한지 너무 오래됏다?!?!?!
      • $O(N^2)$ 구현으로 어케든 짜보자...
      • 생각보다 직관적으로 짜니까 나오네. 길이랑 최댓값 저장해두고 달리기
    • https://boj.kr/2631 줄세우기 (G4)
      • 엥? 이것도 똑같이 LIS인데? 전체 인원수에서 LIS 길이 빼면 되는듯?
      • 엥??????? 코드도 진짜 마지막에 출력 하나 바꿨는데 맞았다... 이건 난이도 거품이 좀 있네...
    • https://boj.kr/2302 극장 좌석 (S1)
      • 음. VIP 없는 각각의 자리에서 나올수있는 경우의수들을 각각 곱해주면 되겠다.
      • 그리고 -1, +1로만 움직일수 있다는건 바로 붙어있는 두명을 바꾸는 경우의 수만 가능하다는거구나.
      • N명의 일반 손님이 붙어있을때 자리바꾸는 수열 만들순있겠지만.. 귀찮으니 재귀로 풀어버리자 ㅎㅎ
      • 근데 짜다보니 피보나치네.. 그냥 바텀업하기..
  • 그래프
    • 이분 매칭
      • https://boj.kr/11377 열혈강호 3 (P3)
        • 이분매칭.
        • 각자 돌리는게 우선이니 한번 돌리고, 더돌릴수있나 한번더 메이킹
        • 이분매칭은 이제 익숙해졌으니.. 템플릿에 넣을까..

03/21

  • 슬라이딩 윈도우
  • 해 구성하기
    • https://boj.kr/20311 화학 실험 (G5)
      • 그냥 제일 많은애들부터 정렬해서 1 3 5 7... 꽂고 2 4 6 8... 꽂으면 될거같았다.
      • 이게 되네
  • 트리 DP
    • https://boj.kr/13024 서브 트리의 크기 (P4)
      • 음.. 보자마자 생각난 문제는 https://boj.kr/12817 버스 노선 (P5)
      • 비슷하지만, 버스 노선은 한 노드 기준으로 양쪽에서 두개 고르기, 그리고 이 문제는 한 노드를 포함하는 서브트리 개수 구하기 = (붙어있는 노드들의 서브트리 개수 + 1) 의 곱!
      • 근데 이걸 모든 노드에 대해 구하면 $O(N^2)$로 바로 터져버리니까, 약간 센트로이드? 같은 느낌으로 나는 DP[노드][자신 포함 서브트리 합, 자신 미포함 서브트리 합, 서브트리 가지수] 로 정리해서 풀었다.
      • 이것보다 쉬운풀이 뭐 있었지만.. 저것도 가능한 풀이였는데 오버플로우로 진짜 몇시간을 속썩였는지 모르겠다... C++ 오버플로우 너무 신경쓰이고 어렵다 ㅜ 곱하기는 두개이상 절대 쓰지 않기!!!
      • 1,000,000,007은 제곱했을때 long long형에 닿을락 말락한다. 진짜 조심하자.

04/04

  • http://boj.kr/16238 독수리 (G1) #그리디 #정렬
    • 어제 자면서 생각했는데, 먹는 순서는 상관이 없더라!
    • 먹는것만 정하면, 순서는 상관이 없음
    • 그러면 많이먹으려면? 많은거부터 정렬하고, 양수인동안 계속 먹자. 한번 먹을때마다 나머지는 1씩 다 빠진다.
  • http://boj.kr/15003 Amsterdam Distance (S2) #기하학 #브루트포스
    • 걍 수학이다.. 헷갈리네
    • 무조건 둘중에 안쪽에서 도는게 최소길이일줄알았는데, 아닌갑다. 그래서 그냥 다 돌아줬음.
  • http://boj.kr/17976 Thread Knots (G3) #매개변수탐색 #그리디
    • 신촌 캠프때 파라메트릭 한번 데인 이후론 진짜 잘보인다!
    • 이 길이로 되나? 되나? 를 테스트해보면 되니까.
    • 시간복잡도는 헷갈리긴 하는데.. $O(NlogNM)$ 인듯? 정렬하는데 NlogN, 탐색에 logM
  • http://boj.kr/2994 내한 공연 (P5) #배낭문제
    • 무조건 가능하다고 했으니까, 결국 N만 가장 효율적으로 채우면 된다!
    • 하나에 잘 채우면, 나머지 하나는 자동으로 결정
    • 그러면? 배낭문제로 배낭을 가장 무겁게 잘 채워보자.
    • 그리고 역추적만 하면 깔끔하다. 문제 교육적이고 좋은듯
  • http://boj.kr/25320 SCV 체인 (P4) #해구성하기 #그리디
    • 어렵다. 아이디어는 바로 떠올려도, 구현을 어떻게할지가 상당히 막막하다.
    • 반례처리도 빡세고, 솔직히 파이썬이니까 그나마 편하게 구현했지 c++이엇으면 더 고생했을듯

04/05

  • https://boj.kr/9369 암호 깨기 (G3) #구현
    • 아 미친 진짜 개고생했네
    • 너무싫다 이런문제..

04/06

  • https://boj.kr/13348 Memory Match (S2) #구현 #많은조건분기
    • 아.. 어제 문제 이해 안돼서 고생했네
    • 그냥 구현하면 되지만... 딱 카드가 두장만 남은 상황이라는 반례가 있다.
    • 잘 처리해주기..
  • https://boj.kr/4782 분수 뺄셈 (G2) #수학 #정수론 #브루트포스
    • 수학이다 수학
    •  
    • 루트 안이 음수가 되면 안되니까 B까지만 돌아주면 된다
    • 깔끔하게 풀리는듯?
     

04/07

  • https://boj.kr/27278 영내순환버스 (S1) #수학 #누적합
    • 그냥 뭐 시키는대로 하면 끝
  • https://boj.kr/11567 선진이의 겨울 왕국 (G3) #BFS
    • 괜히 쫄아서 뭔가 신경썼네
    • 그냥.. 돌면 된다.. 정직하게 시키는대로..
  • https://boj.kr/27281 운전병의 딜레마 (G1) #매개변수탐색 #다익스트라
    • 이제는 진짜 웰논으로 느껴지는 파라메트릭 매개변수탐색
    • 최대불편도를 찍고 돌려보면서 하면 된다.
    • 근데, 다익스트라를 그동안 실수하고있었다!!
    • 1, 2, 3, 4번 노드에서 다 5번노드를 갈 수 있는데, 5번노드가 계속 시간이 갱신되고있었다면 5번노드가 큐에 4번 들어가고 계속 돌아버릴지도?!?!
    • 방문했는데 다른데서 온 최단거리에 의해 길이가 줄어있다면 패스하자. 그때 돌리면 된다!
  • https://boj.kr/18882 Cowntact Tracing (S2) #구현 #시뮬레이션 #브루트포스
    • 그냥 딱 첫 소랑, K수 정해주면 $O(NT^2)$ 정도에 돌아간다.
    • 구현에서만 실수하지 않기~
  • https://boj.kr/3108 로고 (G2) #분리집합 #기하학
    • 아우 기하 싫어
    • 근데 기하가 아니라.. 분리집합에서 실수했더라..
    • 머리를 연결해줘야한다! 그리고 마지막에 다 머리를 찾아가줘야한다! 조심하기
  • https://boj.kr/27926 Quartet (G1) #그래프 #그리디
    • https://boj.kr/19535 문제가 생각나는 아이디어.
    • 간선을 기준으로 양쪽을 보자!
    • 와 근데.. 10^9가 3개 더해지면 30억으로 int를 넘는구나.. 맞왜틀 엄청하고있었네 ㅜㅜ 웬만하면 long long 박기..
  • ABC 348
    • 버추얼로 70분정도 잡고 봤다
    • 근데 너무잘봤다!!! 어제 볼걸 아쉽다
    • A - Penalty Kick (01:05) #구현
      • 그냥 뭐 반복문 구현.. 이하생략...
    • B - Farthest Point (02:55) #브루트포스 #기하학
      • N 제한이 작으니까 브루트포스 돌려버리기!
      • $O(N^2)$ 로 돌아간다.
    • C - Colorful Beans (05:08) #맵
      • C 제한이 크니까, 맵으로 관리해주기.
    • D - Medicines on Grid (34:59) #BFS #다익스트라 #우선순위큐
      • 처음에 약간 당황했는데, 결국 특정 칸에서 가장 에너지가 많은게 이득이다!
      • 근데 이걸 무슨 느낌으로 풀까 고민하다가 그냥 BFS를 쳤는데.. 시간초과.
      • 근데 무조건 에너지가 많을수록 이득이다? 어? 이거 다익스트라 반대인거 아닌가?
      • 최대 힙으로 우선순위 큐를 짜서 관리하자! 문제 아이디어 좋은거같다.
      • 근데 이게 의도한풀이도 아니고 시간복잡도가 증명되지도 않았다고 하네. 근데 빨리돌아서 신기해했다고...
    • E - Minimize Sum of Distances (76:15) #트리 #DP
      • 트리DP!
      • 저번주에 풀었던 http://boj.kr/30491 이랑 느낌이 비슷해서, 생각보다는 빠르게 떠올랐다.
      • 같은 문제인데 가중치가 추가된 느낌
     
  •  

저작자표시