본문 바로가기

알고리즘

 (30)
최단 경로 찾기 알고리즘 (다익스트라, 벨만포드, 플로이드 워셜), 관련 백준 문제 파이썬 풀이 3가지 최단 경로 찾기 알고리즘과 각각이 어떤 문제에서 사용되는지에 대한 포스팅입니다 . 1️⃣ 다익스트라(dijkstra) : 대부분의 최단 경로 문제 다익스트라는 최단 경로 찾기 알고리즘 중 가장 빠르기 때문에 대부분의 문제에서 사용합니다. (다익스트라의 시간복잡도는 O(N+ElogE)입니다. 💛 다익스트라 전체 코드 (백준 1753) import heapq V, E = map(int, input().split()) K = int(input()) adjList = [[] for _ in range(V+1)] for i in range(E): u, v, w = map(int, input().split()) adjList[u].append((v,w)) hq = [] visited = [0]*(V+1) h..
[Python] 프로그래머스 level3 자물쇠와 열쇠 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 방법 회전하는 경우는 4가지 이다. 시계 방향으로 4번 하면 그 다음은 반복이다. 회전은 rotation이라는 함수로 구현한다. key를 2차원 배열로 두는 것 보다, 1인 인덱스 쌍 [i, j]를 배열로 저장해두는게 더 편하기 때문에, rotation함수에서 key[i][j] = 1인 인덱스 쌍의 배열을 리턴하게 만든다. key의 i번째 돌기를 비어있는 lock의 첫 번째 칸에 맞출 때, 더해야하는 값 cx와 cy를 구한다. key의 각각에 더해주고, 그 값이 lock의 홈을 맞게 채우는지 + lock의..
[Python] 프로그래머스 level3 [1차] 추석 트래픽 =i+1 or end < i): cnt += 1 answer = max(answer, cnt) return answer
[Python] 프로그래머스 level2 순위 검색 코딩테스트 연습 - 순위 검색["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pytprogrammers.co.kr풀이 방법정확도 검사 통과는 쉬운데 효율성 검사 통과가 어려웠다.........key가 될 값이 많아서 처음에는 arr[java][backend][chicken] 이런식으로 해야하나 했는데, 문자..
[Python] 프로그래머스 level2 메뉴 리뉴얼 programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 풀이 과정 itertools의 combinations를 이용한다. (가능한 조합을 모두 찾아준다.) collections의 Counter를 이용한다. (리스트의 각 원소의 개수를 key-value 형태로 저장한다.) 각 coures에 대해 반복문을 시행하면서 각 orders에서 combination으로 coures에 있는 개수로 조합을 모두 찾는다. 각 coures에 대해 찾은..
[Python] 프로그래머스 level2 문자열 압축 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 방법 1개~절반의 개수로 압축할 때의 문자열 길이 중 최솟값을 return한다. 문자열 비교는 슬라이싱을 이용한다. 전체 코드 def solution(s): res = len(s) for cut in range(1, len(s)//2+1): answer = '' cnt = 1 last = s[:cut] for i in range(cut, len(s), cut): ..
[Python] 백준 15684 : 사다리 조작 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 방법 i에서 출발했을 때, 어디서 끝나는지 return해줄 함수가 필요하다. board[a][b] = 1은 a번 점선 위치로 b에서 b+1로 갈 수 있음을 의미하고, board[a][b] = -1은 a번 점선 위치로 b에서 b-1로 갈 수 있음을 의미한다. board[a][b] = 0이라면 a번 점선 위치로 b세로줄에서 갈 수 있는 곳이 없음을 의미한다. 브루투포스를 이용해서 아직 연결되지 않은 가로줄 중 3개 이하를 뽑았을 때, i에서 시작하면 i로 끝나..
[Python] 백준 17609 : 회문 풀이 방법 투포인터로 하나씩 비교한다. 만약 좌우가 다른 문자가 나올 경우, left+1해서 검사하고 right-1해서 검사한다. 두 검사 결과 중 하나라도 회문이라면 유사회문이다. 전체 코드 def check(left, right): while left < right: if s[left] == s[right]: left += 1 right -= 1 else: return False return True def twopointer(left, right): while left < right: if s[left] == s[right]: left += 1 right -= 1 else: if check(left+1, right) or check(left, right-1): return 1 return 2 ret..
반응형

티스토리툴바