본문 바로가기

전체 글

[Error] RuntimeError: Failed to import transformers.integrations.bitsandbytes because of the following error (look up to see its traceback): CUDA Setup failed despite GPU being available. Please run the following command to get more information: LLM을 finetuning할 경우, 보통은 GPU가 있는 서버에서 돌리는 것이 현실적이다. llama 2의 경우도 가장 작은 경우가 70억 parameter를 가지므로, GPU가 있는 서버에서 진행하게 되고, GPU 메모리 사용을 줄이고 inference 속도를 높이기 위해 quantized 된 모델을 사용하게 된다. 리눅스에서 finetuning한 모델을 windows에 옮겨서 inference를 진행하려 했을 때 다음과 같은 Error를 마주했다. [Error] RuntimeError: Failed to import transformers.integrations.bitsandbytes because of the following error (look up to see its traceback): C.. 더보기
[Leetcode] 2353. Design a Food Rating System, <Set vs Priority_queue> 문제를 처음 접했을 때는 Priority_queue를 사용하면 풀리는 문제라고 생각하기 쉽다. 그렇지 않은가? highestRated function은 cuisine 분류 별로 제일 높은 rating을 가진 식품의 이름을 요구한다. cuisine 별로 priority_queue로 작성해 두면 쉽게 뽑아 쓸 수 있다. 그런데 문제는 바로 changeRating 함수다. 이 함수는 food의 rating을 변경하여 저장하는 것을 요구하고 있다. Priority_queue는 사용할 수 없을 것 같다. 왜? Priority_queue는 우선 순위대로 값을 정렬하여 보관하고 있다. 기본값은 이다. 즉 내림차순으로 정렬된다는 이야기다. O(logN) operation에 삽입 정렬을 가능하게 해준다. 그런데 문제점은.. 더보기
[Greedy]Leetcode 1727, Largest Submatrix With Rearrangements 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 1) Matrix의 크기가 $10^5$ 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다. 3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을.. 더보기
[Greedy] BJ_21762, 공통부분수열확장, 정올 이 문제는 처음 접했을 때, 어떤 알고리즘으로 문제에 접근해야 하는지 생각하기 난해한 문제다. 제목에서 알 수 있듯이 Greedy 문제로, Greedy 문제는 접근법을 떠올리지 못하면 풀이에 쉽게 다가가지 못한다. 이해를 쉽게 하기 위해 아래 예시를 들어 보자. X, Y를 독립적으로 생각하고, 아래와 같이 주어졌다고 한다면 공통 부분 수열인 w를 중심으로 w의 원소인 w[i]의 사이사이에 어떠한 인자들이 들어갈 수 있는지 계산해 보는 것이 필요하다. 즉 w = da인 아래의 케이스 에는 d의 앞에, d와 a의 사이, a의 뒤에 어떤 알파벳이 들어올 수 있는지를 계산하고 X, Y에 각각 동일한 원소가 있다면 확장 가능한 공통부분 수열이라는 것을 확인할 수 있다. w는 이미 공통 부분 수열이기 때문에 위와 .. 더보기
[Greedy] 백준 25381, ABBC 이 문제의 해결 전략을 뭘까? 맨 처음 의심한 것은 A, B, C 3개중 한개로 입력이 좁혀져서 DP로 푸는 문제라고 생각했으나S의 길이가 30만에 육박한다. dp로 풀기에는 좀 크기가 큰 편이다. 그럼 어떻게? 이 문제는 Greedy 문제로, 핵심관찰이 중요한 문제다. Greedy는 규칙을 발견하면 정말 쉽게 풀 수 있지만, 규칙을 발견하지 못하면 손도 대지 못하는 양날의 검같은 문제가 많다. 그나저나 무엇이 핵심 관찰일까? 1) A, B를 지우거나 B, C를 지우거나 공통적으로 B를 포함하고 있다는 점이다. B의 갯수가 중요하다. 2) 문자열 S에서 A, B를 만들수 있는데 B, C 때문에 못만드는 경우는 어떤 경우일까? A, B에서 B를 B, C로 만드는데 사용하는 경우다. 그렇다면 A, B를 만들.. 더보기
[DP] 백준 28218 격자 게임 어떤 알고리즘으로 문제를 풀어야 할까? 문제의 크기는 300 * 300에, 말의 위치가 다시 원위치로 돌아가는 방법이 없다. 문제를 하위 문제로 나누어 풀어도 문제가 없다는 이야기. 즉, dynamic programming이 가능한 문제라는 뜻이다. 점화식을 어떻게 수립해야 할까? $$ dp[x][y][turn] $$ (x, y)의 위치에서 현재 turn(한국 or 정올)의 차례일 때 이기는 사람의 번호로 점화식을 정의할 수 있다. 그렇다면, 최선을 다한다는 것은 어떻게 표현할까? 현재 첫번째 한국이가 이길 때를 0으로 표시하고, 두번째 정올이가 이길 때를 1로 설정한다. 그리고, 첫번째 한국이의 turn일 때는 정올이가 이긴다고(=1) 초기값을 설정하고 가능한 케이스에서 최소값(=0, 한국이가 이기는 .. 더보기
[Implementation] 백준 28217, 두 정삼각형 이 문제를 풀기 위해서는 삼각형 행렬의 120도 회전과 대칭 operation을 구현해야 한다. 대칭 operation의 경우는 단순히 중간점을 기준으로 좌우를 swap해주면 되기 때문에 생각보다 간단하게 구현할 수 있다. 그런데 120도 회전을 구현하는 부분은 고민이 필요해서 생각보다 시간이 많이 걸릴 수 있다. 삼각형을 3번 회전 시키면 원래 자리로 돌아오기 때문에 우리가 필요한 구현은 삼각형의 120도 3번 회전 했을 때의 배열과 각각 회전한 상태에서 대칭 시키는 구현을 포함해서 총 6개의 행렬만 있으면 비교가 가능하다. A를 모두 회전 시키면 B는 특별히 회전 시킬 필요가 없다. 이 구현만 한다면 나머지는 두 행렬을 비교하는 부분만 남는다. 회전을 구현하는 부분은 다양하게 구현할 수 있는데, 아래.. 더보기
[BruteForce] 백준 28215, 대피소 이 문제는 생각보다 description이 길다. 가장 주요하게 보아야 할 부분은 무엇보다 변수 n의 범위가 50이라는 점이다. 그렇다면 이 문제는 O($n^4$)까지 시간복잡도를 가져갈 수 있다는 것을 의미한다. 중요하게 깨달아야 할 부분을 기술해 보겠다. 1) O($n^4$)의 시간복잡도가 허용되므로, Bruteforce일 가능성이 크다. 2) 거리가 최소가 될 수 있는 대피소의 위치는 "집"에 설치한다고 명기되어 있다 이 부분을 꼭 잘 캐치해야 한다. 즉, 탐색 도메인이 X, Y의 100,000이 아니라 50개의 집의 위치로 좁아지게 된다. 3) X, Y는 서로 연관이 있기 때문에 완전 독립적으로 풀어서는 안된다. 4) 시간복잡도를 줄이려고 median값으로 푸는 것도 시도해 볼 수 있다. 그런데 .. 더보기

티스토리툴바