Slowly, Step by Step

완벽한 bfs 기초문제. 굿 나의 풀이 import deque from collections를 활용하여 queue로 너비우선탐색으로 각 블록별 개수를 가져오는 함수를 작성하고, 해당 함수를 n*n 만큼 실행했다. import sys from collections import deque # n = int(input()) n = int(sys.stdin.readline()) # graph = [[0 for _ in range(n)]for _ in range(n)] # for i in range(n): # graph[i] = list(map(int, input())) graph = [list(map(int, input())) for _ in range(n)] # graph = [list(map(int, inp..

8단 변속기 import sys nums = list(map(int, input().split())) asc = 0 asc = [1,2,3,4,5,6,7,8] dec = [8,7,6,5,4,3,2,1] if (nums == asc): print("ascending") elif (nums == dec): print("descending") else: print("mixed") 다른 풀이 sorted 를 사용해서 비교하는 로직 ascending = sorted(order) descending = sorted(order, reversed=True)

바이러스 이거는 너무 쉬웠어서 3분컷. 어떤 수학의 공식을 이용해서 나온 수식인데 아무튼 나누는 수식을 처음에 해도 무방한 결과값이기에 시간복잡도를 노리면서 나온 문제임 import sys k, p, n = map(int, input().split()) ans = 0 for _ in range(n): k = k * p % 1000000007 print(k)

왜 Level2인데도, 다 쉽게 풀리지는 않는걸까!!! 1. 금고털이 문제 풀이 "베낭에 담을 수 있는 가장 비싼 가격을" 출력하라. 했으니, 그리디 문제이다. 1. 금속들을 정렬한다. - 비싼 가격들로, 그리고 무게는 아래로 - array.sort(key=lambda a: a[0]) import sys w,n = map(int, input().split()) golds = [] for _ in range(n): m, p = map(int, input().split()) golds.append([m,p]) # 금속들을 정렬한다 가장 비싼 가격 그리고 무게는 아래로 golds.sort(key= lambda a:(-a[1])) # print(golds) remainedW = w totalPrice = 0 t..

투 포인터 알고리즘 배열 또는 리스트에서 두 개의 포인터(인덱스) 사용하여 문제를 해결하는 알고리즘. 사용하는 상황 정렬된 배열에서 순회하거나 검색할 때 사용된다. 완전탐색 시간복잡도가 너무 클 때 생각해볼 수 있음. 단 정렬을 하고 사용해야 한다. 시간 복잡도 O(N), O(logN) 예제 1. 정렬된 배열에서 두 숫자의 합이 특정한 값이 되는 두 숫자를 찾는 문제 function twoSum(nums, target) { let left = 0; // 배열의 시작에서 시작하는 포인터 let right = nums.length - 1; // 배열의 끝에서 시작하는 포인터 while (left < right) { const sum = nums[left] + nums[right]; if (sum === ta..

다익스트라 알고리즘에서 우선순위 힙을 이용한 부분을 정리한다. 1. 힙, 우선순위 큐 힙과 우선순위 큐의 관계는 다음과 같이 정의할 수 있다. 힙이라는 자료구조를 사용해 우선순위 큐를 구현한다. 그리고 구현된 우선순위 큐는 Python에서 PriorityQueue, heapq 라이브러리 형태로 제공되며, 이 우선순위 큐를 가지고 다익스트라 알고리즘의 병목현상을 개선한다. 이 때, 병목현상이란 저번 포스팅에서 언급했지만 기존의 다익스트라 알고리즘의 문제점 중 하나는 알고리즘 반복 단계에서 시작 노드와 가장 거리가 짧은 최단 거리 노드를 찾아야 하는데, 이 때 매번 선형탐색을 수행했어야 했다는 것이다. 그렇다면 우선순위 큐는 무엇일까? 힙이라는 자료구조로 구현된다. 이렇게 힙으로 구현된 우선순위 큐는 어떤 ..

String Matching 아이템을 적절히 고르는 문제 지금까지 선택한 동전의 합이 i 라 했을 때, 가능한 최대 동전의 개수 이렇게 테이블을 만든 이유 : 문제에서 동전의 최대 개수를 구하는 것이기 때문에 돈을 작은 돈 부터 풀어나가자는 바텀업으로 진행, 동전의 합에 따른 최대 개수를 그대로 테이블화 점화식 만들 때 1. 상황 나누기 마지막 상황 즉, 마지막에 무엇을 더하는 것에 따라 조건문을 만든다. 10을 거슬러줘야 할 때, 이런 경우의 수가 있다. 2+2+2+2+2 2+2+3+3 2+4+4 3+3+4 어떻게 나눠야 할까? 마지막에 선택되는 동전으로 나누기 2+2+2+2+2 / 2+2+3+3 / 2+4+4 3+3+4 2. 하나의 상황에 대한 점화식 마지막으로 2를 더하는 모든 상황 중, max를 ..

Dynamic Programming 이란 완전탐색의 비효율성을 해결하기 위해 동적으로 계획해서 계산하는, 알고리즘 1. Subproblem을 그대로 합치면 되는 DP N번째 원소 구하기 - Backtracking N번째 원소 구하기 - DP 구현 1 - Memoization 점화식을 쭉 계산할 때 같은 계산이 반복될 수 있다. 아래 그림에서 F(4)가 왼쪽 트리에도 있고 오른쪽 트리에도 있는 것을 확인할 수 있듯이 같은 계산이 반복될 수 있어서, 모든 노드를 보는 계산은 비효율적이다. 따라서, 같은 계산 반복됨을 피하기 위해 나온 방식이 Memoization 계산한 적이 있으면 기억하기 1. Memo라는 기억배열을 생성한다. + 초기화 -1값으로 (계산에서 절대 나올 수 없는 값인 -1로 초기화) 2. ..

문제 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1) X가 5로 나누어떨어지면, 5로 나눈다. 2) X가 3으로 나누어 떨어지면, 3으로 나눈다. 3) X가 2로 나누어 떨어지면, 2로 나눈다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라. X = 26일 경우 1. 26 - 1 = 25 2. 25 /5 = 5 3. 5 / 5 = 1 입력 첫째 줄에 정수 X이 주어진다. (13->5 1 빼는 것을 디폴트로 넣고 2,3,5는 나누어 떨어지는 경우에만 들어간다. 3. bottom up 형식 이용하기 나는 dp[6]을 얻고 싶을 때 dp[5]와 d[6/2] d[6/3] d[6/5]..

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4 =0 and x