본문 바로가기

전체 글276

[Linalg] LU Decomposition LU Decomposition (프로그래머스 2주차 Day2 - LU Decomposition 내용) 행렬의 분해 행렬의 분해는, 행렬을 곱으로 분해하여, 계산한다. 대표적인 행렬 분해의 예시는 다음과 같다. - LU 분해 (가우스 소거법을 행렬의 형태로 적음) - QR 분해 (직교 분할과 관련) - 특이값 분해(SVD) 오늘은 LU 분해에 대해서 알아본다. LU분해 LU 분해란, 주어진 행렬을 하삼각행렬 * 상삼각 행렬 형태로 쪼개는 것을 말한다. 만일 이것을 했을 경우, 어떤 장점이 있을까? Ax = b -> (LU)x = b -> L(Ux) = b -> 상삼각이나 하삼각 형태이므로 해를 구하기가 간단해진다. 이 때, LU분해의 과정에서 행끼리 바꿔줘야 하는 경우가 존재한다. 이는 치환행렬을 곱하는 .. 2021. 4. 26.
[Linalg] 선형시스템 및 가우스소거법 (Numpy Code 추가) (프로그래머스 2주차 Day1 수업정리) 선형시스템 및 가우스 소거법 기초부터 튼튼히 기초부터 튼튼히 - 중,고등학교때 배웠던 연립방정식이 선형시스템(linear system) 이다. 그런데 , 문제는 변수가 훨씬 더 많이지는 등의 어려운 점이 발생한다면, 중고등학교때 배운 가감법으로는 무리일 것이다. 오늘의 목표 (1) 선형시스템, 즉 Ax = b의 정형적 풀이법을 알아보자. (2) 가우스 소거법에 대해 알아보자 (3) 이에 대한 코드 구현법을 알아보자. 선형 시스템 -> 행렬 표현 우선 이를 위해서는 일반적인 연립 방정식을 행렬 형태로 표현해야 한다. 이는 다음과 같은 식으로 한다. 계수는 계수끼리, 상수는 상수끼리 모아서 행렬로 표현하면 된다. - 식은 행이다. - 식이 m개고, 미지수가 n개일 경.. 2021. 4. 26.
[Python] 프로그래머스 Lv 4 - 버스여행 즐거운 BFS 문제 프로그래머스 Lv 4 버스여행 문제 알고리즘 갈 수 있는 루트가 있는지 버스가 많아질수록 일반적인 확인은 어렵다고 판단, BFS를 사용하기로 했다. 조금 걱정된 부분은 버스가 많을때 visited가 커지면 복잡도 면에서 걱정이 되었는데 set으로 처리를 해서 복잡도 면에서 조금 이득을 보는 구성을 사용하였다. 코드 from collections import deque def can_reach_bfs(start, end, signs): visited = set() queue = deque() queue.append(start) while queue: next = queue.popleft() visited.add(next) for i in range(len(signs)): if i == .. 2021. 4. 25.
[Python] 프로그래머스 Lv 3 - 자물쇠와 열쇠(2020 카카오 코테 기출) 2020 카카오 블라인드 채용 코테 기출문제 자물쇠와 열쇠 풀이 어려운 아이디어 보다는 쌩 구현력을 묻는 문제로, 리스트가 왔다갔다 하는 상황이 많아서, 어떻게 대처해야 할지를 잘 고려해야 하는 문제이다. 함수로 잘 쪼개야 한다. 다행히 좌표 장난질은 덜하되, 알고리즘 (1) 일단, 열쇠가 삐져나와도, 구멍에만 정확하게 맞게 끼워주면 된다는 의미는, 열쇠가 바깥으로 벗어날 수 있다는 점이다.따라서, 자물쇠의 판을 넓혀서 양쪽으로 열쇠가 자연스럽게 들어갈 수 있게 해주자. (2) 열쇠를 1번 돌려서 넓게 핀 자물쇠칸 각 칸에 모두 꽂아보고, 안되면 열쇠 돌리고 총 열쇠를 4번 돌려서 다 안되면 실패로 False를 return 해버린다. 이 때, 자물쇠의 첫 칸을 변수로 줘서 다음 번 시도에도 편리하게 넣을.. 2021. 4. 24.
[Python] 프로그래머스 Lv 2 - 최대 용량이 정해진 FIFO 큐 클래스 스택 2개로 큐를 만들 수 있다? 이에 대해서 알아보자. 프로그래머스 Lv 2 최대 용량이 정해진 FIFO 큐 클래스 문제풀이. 풀이 방법 스택 2개를 준비한다. 각각 1번스택, 2번 스택이라고 하자. (1) 삽입의 경우 최대 용량까지만, 1번에 무조건 넣는다. (2) 삭제의 경우 1번의 바닥의 거를 꺼내는데, 이는 다음과 같이 한다. - 바닥까지 모두 다 순차적으로 꺼내서 2번 스택에 넣는다. - 2번 스택의 가장 윗부분은, 1번 스택의 밑부분이다. 2번에서 다시 pop을 한다. - 2번 스택에 남은 거를 모두 1번으로 옮긴다. 다시 돌려놔야 하는걸 잊지말자! 코드 # Stack 2개로 queue를 구현할 수 있다? ㅋㅋ루이지 class MyStack(object): def __init__(self):.. 2021. 4. 24.
[Python] 프로그래머스 Lv 3 - 게임아이템 Heap을 활용하는 또 다른 문제 프로그래머스 Lv 3 게임아이템 풀이 출처 : 프로그래머스 스쿨 알고리즘 우선 포인트는 다음과 같다. (1) 템 어차피 1개 밖에 못 낀다. (2) 남이 못 낀 템, 내가 HP가 충분하면 먹을 수 있다. (3) 그런데 먹을 수 있는 템 중에선 제일 좋은거를 껴야 한다. 따라서 다음 순서대로 푼다. (1) 캐릭의 HP와 item을 정렬한다. (1)-1 이 때, item에는 체력, 공격력, index를 부여하는 새로운 item list를 만든다. enumerate를 활용하자. (1)-2 다중리스트여도 별 조건 없으면 첫 성분의 오름차순 기준으로 정렬된다. 따라서 깎이는 HP를 맨앞에 쓴다. (2) 캐릭별로 한명씩 item 착용을 시도한다. 이제 낮은 hp를 가진 사람은 hp.. 2021. 4. 23.

티스토리툴바