Algorithm(Py)

처음에 dp를 값 다 저장하는 방식으로 구현했다가 시간 초과 났던.....

오늘 코드 리뷰하다 깨달은 사실 ord() - 알파벳을 입력 받아 아스키 코드로 변환 chr() - 정수를 입력 받아 아스키 코드 문자로 변환 이걸 몰라 dictionary에 다 때려박던 날들이여 안녕~

처음에 row별 누적합 구하고 슬라이싱 하는 방식 썼다가 시간 초과남..

다익스트라 최단 거리 알고리즘. 다만 간선의 가중치가 음수일 땐 사용할 수 없음. 출발 노드 설정 출발 노드부터 각 노드까지의 최소 비용 저장(미방문 - 무한대로 저장) 방문하지 않은 노드 중에 제일 비용 적은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 경우 고려해

첫 제출다익스트라를 썼는데 다익스트라는 한 노드에서 다른 노드까지의 최단 거리를 구하는 것이지 그 사이에 몇 개의 노드를 거쳤는가는 파악이 안 되기 때문에 틀렸다.수정(다익스트라 3번)시작점에서 출발하는 다익스트라v1에서 출발하는 다익스트라v2에서 출발하는 다익스트라각

그래프 탐색 대신 2차원 배열에 델타 탐색 사용하여 다익스트라 구현.다익스트라인 거 알면 쉽게 풀리는데 지금 내가 알고리즘 분류에서 다익스트라만 골라서 푸는 중이라 쉽게 푼 거고 그냥 문제만 봤으면 한참 고민했을 것 같다.

M, N 최대 8인 문제라 이렇게 푸는 게 하단 코드처럼 path와 used 따로 관리하는 것보다 더 빠를 줄 알았는데 아니더라. 아주 근소한 차이로 하단 코드가 더 빨랐다.

두 개의 문자열, str1과 str2를 비교한다. | str1 | C | A | T | S | A | R | E | C | U | T | E | |:-----:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |str2|D|O|G|S|A|R|E|N|O|T| len(str2) 길이를 가진 배열을 len(str1)개 갖고 ...

원래 중간에 디버깅 코드가 있었는데 pq = (1,4), (0, 10), (1,6) 인 상황에서 (1,4)를 제일 먼저 방문하길래 이유를 찾고자 gpt를 닦달했다. 알고보니까 삽입연산 시 heqppush가 아니라 리스트에 pq.append로 냅다 넣어서 트리 구조가 꼬

냅색이 실타.코드출처

개선된 코드 i+k <= t 를 검사하는 대신 반복문 범위를 k~t까지로 한정하고 돌림

임의의 한 정점에서 가장 먼 정점 a를 구한다.a에서 가장 먼 정점 b를 구한다.a에서 b까지의 거리 == 트리의 지름.처음에 다익스트라로 풀었다가 트리의 지름을 구하는 방법 알고 dfs/bfs 로 전환. 오늘 알게 된 사실 하나 더.파이썬 함수 리턴값 여러 개일 땐

다른 사람들은 비트마스킹 쓴 거 같길래 머리 싸매다가 대각선 체크를 O(1)로 하는 법 깨닫다.우상향 대각선의 경우 같은 줄 내에서 (x, y)의 x+y 값은 항상 같게 유지됨.우하향 대각선의 경우 같은 줄 내에서 (x, y)의 x-y 값은 항상 같게 유지됨.a. 이

벽을 부순 경우(랄프한 경우)와 아닌 경우를 나눠서 방문 체크하며 bfs 돌리기주먹왕 랄프

처음에 2차원 배열로 만들었다 중복 체크로 인해 오류 났었음.가로/세로/대각선 어느 방향에서 왔는지에 따라 다르게 분기처리.

빡구현.. 이거 맞나.. 분명 더 효율적인 방법이 있을 거 같은데 다시 풀어봐야겠음

알게된 점 : |으로 끝나면 공백문자까지 찾으려고 한다.

fullmatch : 문자열이 처음부터 끝까지 패턴과 일치하는지 확인

python의 리스트는 동적 배열로 메모리 할당은 다음과 같은 방식으로 이루어진다.1\. 생성 시 용량 02\. 첫 append() 시 기본 크기 할당. 기본 크기란? python의 리스트는 동적 배열이기 때문에 C++의 array처럼 요소 개수에 맞추어 용

시간 초과 줄이려고 비트마스킹 쓰고 여러가지 해봤는데 결론은 python3으로는 통과 못하고 pypy 써야만 하는 문제였다. 붙잡고 있던 시간이 아까워

틀린 내역사전 순으로 가장 늦게 오는 부분 수열을 찾는 문제.처음엔 두 수열을 뒤부터 돌면서 공통 값이 있고, prev보다 크면 res에 넣는 방식을 썼는데 이런 저런 오류가 많이 났다..비내림차순이 사전 순 최대 값을 보장하지 못하는 문제 등두 수열의 최댓값을 비교한

기본적으로 dfs/bfs 알고리즘은 노드 방문 -> 방문 처리인접 노드 확인 시 방문 여부 체크한 뒤 미방문 노드만 탐색이라는 과정을 거친다.그런데어떤 문제는 ‘현재 경로에서만 방문했는지’를 기준으로 판단하는 경우가 있다. 즉, 전역 방문 배열이 아닌, 경로별로 따로

풀이 BFS: 현재 지점 기준으로 가장 가까운 인접한 노드들 탐색 1.1. 최단 거리 물고기보다 현재 노드까지의 거리가 더 멀다면 탐색하지 않음 1.2. 만약 인접 노드에 먹을 수 있는 크기 물고기 있다면 fish에 넣기 1.3. 가까운 순, 위에 있는

메모리초과, 시간초과, 스택오버플로우 다 겪고 나온 코드...기본적으로 이진 검색 트리를 전위 순회하면노드+왼쪽 서브 트리(노드보다 작은 값)+오른쪽 서브 트리(노드보다 큰 값) 으로 구성되게 된다.그래서 노드 다음 인덱스들을 탐색하되 노드보다 값이 커지는 순간이 오른

슬라이싱 인덱스 범위를 초과하는 숫자를 써도 인덱스 에러가 나지 않기에 매우 애용했었다. 하지만 해당 요소까지 메모리를 복사 후 재할당하기 때문에 O(N)이라는 시간 복잡도를 지닌다.입력받는 문자열 길이가 최대 백만, 시간제한 2초인 문제로 O(2N)안에 해결해야 한다

풀이 코드 처음에 half를 쓰지 않고 같은 식으로 했다가 시간 초과 났었다.. 저장하자..

각 인덱스 별로 dp를 통해 0~i까지의 최장 증가 부분수열과 i~N까지의 최장 감소 부분수열을 구한 뒤 합친 값의 최댓값을 구한다.

최단 경로 여러 개를 모두 탐색할 수 있도록 종료 조건을 설정하기.

다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV)이를 노드마다 실행하므로 O(V\*(V+E)logV)해당 문제에서sms 1 <= n <= 100, 1<= r <= 100 이므로O(100\*200\*log100) = 140,000 정도.

범위 처리 꼼꼼하게 하기!