전체 글
-
[Python] 프로그래머스 / 순위코딩테스트 2024. 9. 17. 23:47
문제 링크 여기서 Floyd-Warshall이?갑자기 웬 플로이드-워셜인가 싶을 것이지만, 이 문제를 찬찬히 살펴보면 알게 될 것이다. Floyd-Warshall 알고리즘의 본질은, i-j의 관계를 모르더라도 i-k, k-j 사이의 관계를 알면 결국 i-j 사이의 관계를 알게 된다는 것이다. 그러므로 이 알고리즘은 비단 "거리"나 "cost"에 한정된 아이디어가 아니다. 예를들어 이는 부등호 관계에서도 성립되는 아이디어이다. i > k, k > j 를 알고 있다면, i > j 또한 알 수 있게 되기 때문이다. 정답 코드def solution(n, results): graph = [[0] * n for _ in range(n)] for A, B in results : ..
-
[Python] 프로그래머스 / 섬 연결하기코딩테스트 2024. 9. 17. 21:52
문제 링크 최소 스패닝 트리문제를 읽자마자 대놓고 "최소 스패닝 트리로 풀어!" 라고 말하고 있다.최소 스패닝 트리(MST) 문제는 Prim 알고리즘과 Kruskal 알고리즘으로 풀 수 있다.Prim 알고리즘 : 임의의 정점에서 시작해서 가장 가까운 이웃 정점을 고르고, 다시 그 정점에서 가장 가까운 정점을 고르기를 반복하는 것Kruskal 알고리즘 : 간선 중 짧은 것부터 고르는 것. 다만, Cycle이 형성되면 안 됨.Cycle이 형성되면 안 된다는 문제점 때문에 (이게 생각보다 코드 구현이 빡세서), 보통은 Prim 알고리즘이 선호된다. 여기에서도 Prim 방법을 쓸 것이다.비슷한 백준 문제를 Kruskal 알고리즘으로 푼 포스트는 다음 링크에 있다:https://loewen.tistory.com ..
-
[Python] 프로그래머스 / 거스름돈코딩테스트 2024. 9. 17. 20:53
문제 링크 생각보다는 어려웠던 문제.사실 이런 유사 문제는 DP 아니면 BFS일 때가 많고, 그중에서도 어지간하면 DP일 때가 많기는 하다.이 문제에 BFS가 안 통하는 이유는, 순서가 상관없는 조합 문제이기 때문이다. 아래의 그림은 2원과 3원으로 10원을 만드는 조합이다.2와 3으로는 2+2+2+2+2, 2+2+3+3와 같이 총 두 가지의 방법으로 10을 만들 수 있는데, 이는 아래의 그림과 같이 표현된다. 이를 코드로 표현하면 다음과 같다:def solution(n, money): dp = [1] + [0] * n for money_type in money : for i in range(money_type, n+1) : dp[i] += dp[i - ..
-
[Python] 구간 최댓값 문제 풀이코딩테스트 2024. 9. 16. 15:47
구간 최댓값과 세그먼트 트리잊을만하면 나오는 "구간 최댓값" 문제. 구간 최댓값, 구간합, 구간 최솟값 같은 문제는 세그먼트 트리 방식을 사용하는 것이 시간 복잡도 측면에서 유리할 때가 많다. 이를 트리 구조로 다시 봐보자. 세그먼트 트리이지만, 개인적으로는 트리가 아니라 리스트 방식으로 보는 것이 이해가 훨씬 더 수월했다. 보는 바와 같이 인덱스 1부터가 사실상 시작인데, 이는 트리 구조에서 인덱스 1을 root node로 놓으면, 2x하면 왼쪽 자식, 2x+1 하면 오른쪽 자식이 되어 계산이 편해지기 때문이다. 그럼 [1, 3, 5, 7, 9, 11] 중 index range(1, 4), 즉, [3, 5, 7] 의 최댓값을 찾아보자.1. 우선 우리가 구하고자 하는 구간 최대값 \(x = - \inf..
-
Bergeron 논문 Ablation Study 해보기논문 후기와 구현 2024. 9. 15. 21:30
JailbreakingDiffusion 모델 등 생성형 모델은 본질적으로 인간의 통제가 온전히 개입할 수 없는 부분이 있다. 그러나 그렇다고 해서 손 떼고 있을 수만은 없다. 최근 소위 "딥페이크 범죄"가 크게 이슈가 되고 있듯이, 생성형 인공지능에 대한 통제를 포기한다면 사회는 큰 혼란에 빠질 것이기 때문이다. 현재로서는 보통은 (특히 언어모델은) fine-tuning을 이용해서 유해정보 생성을 억제하는 것이 최선이다. 예를 들어 ChatGPT에게 폭탄 제조법을 물어보면 안 알려주는데, 이는 해당 질문에 대해 대답을 하지 못하도록 fine-tuning된 것이다. 이렇듯 유해정보 생성을 하도록 유도하는 것을 Jailbreaking이라고 하는데, Jailbreaking 및 그에 대한 Defense 연구 논..
-
[Python] 프로그래머스 / PCCP 기출문제 / 퍼즐 게임 챌린지코딩테스트 2024. 9. 14. 21:07
문제 링크 프로그래머스 PCCP 문제가 으레 그렇지만, 문제만 읽고는 도통 문제 해석이 쉽지 않다. (얘넨 항상 이런 식임). 이럴 때에는 문제에서 친절하게 제공해주는 예시를 철저히 분석해야 한다. 어차피 방정식이 아닌 이진탐색으로 문제를 풀 것이지만, 방정식으로 문제를 이해해보자.1번 문제의 답, 즉 숙련도를 \(x\)라고 해보자. 그러면 총 소요되는 시간은 다음과 같다: i) \(3 \leq x 2번 퍼즐만 숙련도를 초과하므로 추가시간이 소요된다.즉 총 소요되는 시간은:\[2 + (4 + (5 - x) \times (2 + 4)) + 7 = 43 - 6x\]여기서 \(43 - 6x ii) \(1 \leq x 2번과 3번 퍼즐이 숙련도를 초과한다.그러면 총 소요되는 시간은:\[2 + (4 + ..
-