CS/Algorithm
다익스트라 알고리즘
다익스트라? # 다익스트라? (데이크스트라 라고도 불린다.) # 출발점이 정해져있을때 출발 노드로부터 다른 노드에 이르기까지의 최소비용 # 1. 출발지를 기준으로 인접노드를 살펴본다. # 2. 간선에는 비용이 적혀있다.디폴트값은 무한대. # 3. 이동하고 가장 작은 값으로부터 인접한 노드의 비용의 누적합을 다시 체크한다. 그림으로 보자면 이렇다. s 노드에서 출발할때 인접한 두 노드 까지의 비용을 각각 입력한뒤, 그 다음으로 가장 작은 비용을 가진 y노드에서 다시 인접한 노드까지의 비용 누적값을 계산하여, 기존의 것보다 작다면 바꾸어주고 y노드의 값을 고정시킨다. 마찬가지로 다시 다음으로 작은 노드인 z로 이동한 다음, 인접한 노드까지의 비용 누적값을 계산한다. 그 값이 기존의 것보다 작다면 바꾸어주고 ..
[이코테,python] 볼링공 고르기
처음엔 그냥 무지성으로 이중 포문으로 풀었다. n, m = map(int, input().split()) weights = list(map(int, input().split())) # sol1) n^2 lst = [] cnt = 0 for i in range(n): lst.append(weight[i]) for i in range(n - 1): for j in range(i + 1, n): if lst[i] != lst[j]: cnt += 1 print(cnt) 풀고나서 다른사람들의 풀이를 보았는데, 이런 문제의 경우에 수학적 사고를 통해서 시간 복잡도를 n으로 줄일수 있는것을 알게 되었다. n, m = map(int, input().split()) weights = list(map(int, input(..
[프로그래머스, python]2020 KAKAO BLIND RECRUITMENT문자열 압축
# 문자열을 1,2,..,n//2 개씩 나눠서 리스트에 넣고, # 리스트 원소끼리 비교해서 같다면 다음것까지 비교하면서 cnt++해준다. # 만약 다를경우 cnt+문자열을 pop하고 temp에 넣는다. 다시 반복하다가 끝까지 확인하고, join하여 # answer list에 append시키고, 상황을 n//2개씩까지 간후에, 가장짧은 길이의 리스트 원소를 출력해준다. 라는 생각을 가지고 접근하였다. def slicing(q, cnt, temp): if len(q) 1: head = str(cnt)# 숫자를 그대로 붙이기 위해서 temp += head + q[0] else: temp += q[0] return len(temp) if q[0] == q[1]: # 처음원소와 다음원소가 같다면. cnt += 1..
[프로그래머스,python] 2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠
key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다. # 1. 회전하는 매커니즘 # 2. 상하좌우로 가는 매커니즘 >> pop하고 0을 appendleft하거나 popleft하고 0을 append # 3. ** lock의 0이 있는 패턴을 저장해 ** # key에서 1이 있는 패턴이 위에서 구한 패턴과 같은지 봐. 없으면 회전시켜봐. # 회전3번 해도 없으면 false를 리턴해. # 4. 패턴이 존재한다면 두 이차원 배열끼리 포개서 합쳐. # 만약 포개서 합칠때 2가 있다면 다시 회전해서 패턴을보고, 끝까지 없다면 다시 false를 리턴해. # def solution(key,lock): def rotated(key): #..
[python] 연결 리스트, 삽입 정렬 Leetcode 147
파이썬 알고리즘 인터뷰 60번 문제입니다. 처음 접근할때 연결리스트가 미리 쓸수 있게 되어있지 않아서 설마 내가 연결리스트도 구현해줘야하나? 하는 뭔가 이상함을 느끼고 input을 print로 찍어봤는데 저렇게 줬더라.. input이 list 인것 처럼 해놓고 저렇게 주면 너무 문제를 위한 문제가 아닌가? 라는 생각에 직접 input을 연결리스트로 만들어주고 그 연결리스트를 삽입정렬을 하려고 했다. 처음 생각은 node의 value를 전부 받고 비교해서 스왑을 하려고 아무리 생각을 해봐도 모르겠었다.. 그래서 예비책으로 생각을 해본게 n번째 노드와 n+1번째 노드를 비교하고 2가 더 작다면 remove하고 그걸 다시 insert할 자리를 head로 넣어줘야 하는데 그렇게 하면 그건 삽입정렬이 아니게 되니..