🔗 Algorithm/Python

[Python] 프로그래머스 지형 이동

문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 계속 틀려서 다른 사람의 풀이를 보고 푼 문제이다. 어떻게 이런생각을 떠올리지...? heap을 사용해서 풀었다. 상,하,좌,우 칸 중에 방문하지 않은 칸과의 길이가 height보다 크다면 heap에 차이와 점을 기록한다. height보다 작다면 0과 점을 기록한다. 이를 이용해서 min heap으로..

[Python] 프로그래머스 합승 택시 요금

문제에 대한 자세한 설명은 아래 링크 참조 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr Dijkstra 알고리즘을 사용해서 풀었다. (최단거리..

[Python] 백준 7453

세상 복잡하고 까다로웠다.. 이것 저것 시도해보았는데 12초나 주어진 시간이 자꾸 초과돼서 이틀이나 걸린 문제,, 비슷한 유형의 문제가 많다. 백준 1208번 문제도 같은 유형이므로 유형에 대한 설명은 아래 링크에서 참조 📌https://990427.tistory.com/48 [Python] 백준 1208 구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하 990427.tistory.com 우선 1208번과 같이 딕셔너리를 사용해서 문제를 풀었더니 시간초과가 났다. 이유는 정말 모르겠다... 딕셔너리의 시간복잡도가 O(1)이긴 하지만 숨어있는 상수가 매우 크다고 한..

[Python] 백준 1208

구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다. 이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다. 그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다. (2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ? 나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에) key : 부분 수열의 합 value : 해당 부분 수열의 합이 나온 횟수 예제를 예로 들어 코드 설명을 하자면 우선 l=[..

[Python] 백준 1167, 1967

입력값의 차이 외에는 똑같은 문제이다. 먼저 트리의 지름을 찾는데에는 rule이 있다. ✔ 트리에서 임의의 노드(A)를 선택해 가장 먼 노드를 찾는다. -> B ✔ B에서 가장 먼 노드를 찾는다. -> C ✔ 그러면 B와 C사이의 거리가 가장 멀다. (==지름) 이 규칙을 알면 쉽게 쉽게 풀 수 있겠다. 모르면 ㅠㅠ 삽질 하니까 알고있자... Answer 1167 import sys from collections import defaultdict from collections import deque n=int(sys.stdin.readline()) dic=defaultdict(list) for i in range(n): l=list(map(int,sys.stdin.readline().split())) a..

[Python] 백준 10917

어려웠던 문제는 스스로 솔브해도 다른 사람 풀이랑 비교하기 위해서 검색을 해보는데 푼 사람이 별로 없어서 검색해도 안나와서 슬펐당... 내 답이 최적인지는 모르겠으나 일단 풀었고 푼 사람이 별로 없어서 나라도 리뷰를 써놔야지,,😇 일단 나는 BFS + 우선순위Q로 풀었다. 딕셔너리를 만들고 x를 key로 y를 value로 두고, value는 우선순위Q 내림차순으로 저장했다. (꿈은 더 큰 수로 이동하고 N이 가장 크기 때문에 N을 가지고 있다면 바로 그만 할 수 있게하기 위함) 그리고 queue에 현재 위치와 현재 상황이 바뀐 횟수를 저장하며 BFS를 한다. N을 만나면 그만한다. (bfs니까 처음만날 때 최소) Result import sys from collections import defaultdi..

[Python] 백준 2089

덕분에 파이썬에서 a//b가 어떻게 동작하는지 정확히 알 수 있었다. 이렇게 동작한다고 한다. import sys n = int(sys.stdin.readline()) if n == 0: print(0) else: res = [] while n != 0: if n%(-2) == 0: res.append('0') n = n//(-2) else: res.append('1') n = n//(-2) +1 print(''.join(reversed(res)))

[Python] 백준 1442

solution은 간단하게 받은 수 중에서 가장 큰 수를 n-k개 더 만들어 주고 그 수들로 정렬하면 된다. 단, 정렬할 때 문제에서 준 예제와 같이 7 3 2 처럼 주어진 숫자가 같은 자리 숫자라면 상관 없지만 9 90 990 과 같은 숫자가 주어졌을 때 문제가 생긴다. 가장 큰 수 부터 정렬하면 990 90 9 이지만 실제로 가장 큰 수를 만들기 위해서는 9 990 90 와 같이 정렬되어야 한다. 예전에 풀었던 문제에서 해결 방법을 찾았다! num.sort(key = lambda x: x*10, reverse=True) num의 숫자들은 type이 문자열이다. 이 문제의 최대 범위가 1,000,000,000 이므로 숫자의 최대길이가 10이다. 그러므로 길이 10만큼만 비교하면 된다. 예를 들면, 20..

[Python] 백준 6549

교훈 : 플래라고 겁먹지 말자 stack을 이용해서 풀었다 stack 삽입 : index와 높이(h) 원리 : 현재 index보다 stack에 있는 index(나보다 왼쪽)의 h가 더 크면 현재 index의 h값으로 왼쪽도 포함할 수 있다. 더보기 여기서 오른쪽의 높이(2) 로 왼쪽을 포함하여 넓이가 4가 될 수 있다. 이 원리를 이용해 stack으로 풀 수 있었다! import sys while True: #마지막에 stack에 있는 값을들 다 꺼내기 위해 마지막 h값은 0 h = list(map(int, sys.stdin.readline().split())) + [0] if h[0] == 0: break n = h[0] stack = [(1,h[1])] res = 0 for i in range(2,n..

[Python] 백준 2606

BFS또는 DFS를 사용하는 그래프 탐색 문제다. 먼저, 입력받은 데이터는 딕셔너리로 구현하였다. 네트워크는 양방향 그래프 이므로 아래 코드와 같이 딕셔너리에 두 번 입력해야 한다. 그래프 구현 net = {} for i in range(n): a, b = map(int, input().split()) if a in net : net[a].append(b) else : net[a] = [b] if b in net : net[b].append(a) else : net[b] = [a] 같은 네트워크 상에 있는 컴퓨터를 검색하는 알고리즘은 BFS를 사용했다. visit에서 1을 빼면 1과 연결되어 있는 컴퓨터만 남게 되기 때문에 len(visit)-1을 결과로 출력했다. 전체코드 m = int(input())..