Always awake
카테고리
검색하기
죠.
« 2024/09 »
일
월
화
수
목
금
토
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
닫기
관리 메뉴
Always awake 백준 일지 (~04/07) 본문
PS 백준 일지 (~04/07)
죠.
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
슬라이딩 윈도우
해 구성하기
트리 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
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) #맵
D - Medicines on Grid (34:59) #BFS #다익스트라 #우선순위큐
처음에 약간 당황했는데, 결국 특정 칸에서 가장 에너지가 많은게 이득이다!
근데 이걸 무슨 느낌으로 풀까 고민하다가 그냥 BFS를 쳤는데.. 시간초과.
근데 무조건 에너지가 많을수록 이득이다? 어? 이거 다익스트라 반대인거 아닌가?
최대 힙으로 우선순위 큐를 짜서 관리하자! 문제 아이디어 좋은거같다.
근데 이게 의도한풀이도 아니고 시간복잡도가 증명되지도 않았다고 하네. 근데 빨리돌아서 신기해했다고...
E - Minimize Sum of Distances (76:15) #트리 #DP
