본문 바로가기

Algorithm43

[프로그래머스] 12978 파이썬 - 배달 풀이문제를 읽어보면 1번 마을에서 다른 마을까지 거리 중 최단 거리를 구하는 문제임을 알 수 있었다. 이때, 제한사항을 읽어보니 노드(마을의 개수)가 최대 50개임을 알 수 있었다.따라서 다익스트라 알고리즘을 사용하여 풀 수 있는 문제였다. 다익스트라 알고리즘 CT-Study/PART 2/Chapter 9, 최단 경로.md at master · JeongEunJi1127/CT-Study🔎 코딩테스트 공부 결과물 정리를 위한 저장소 . Contribute to JeongEunJi1127/CT-Study development by creating an account on GitHub.github.com- 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘- 가장 비용이 적은 노드를.. 2024. 9. 9.
[프로그래머스] 67256 파이썬 - 키패드 누르기 풀이키패드의 숫자와 각 숫자에 맞는 좌표를 미리 딕셔너리에 선언해두고 풀었다.나머지는 단순 구현이었다.if문을 사용해 조건만 잘 걸어주면 어렵지 않게 풀 수 있는 문제였다. 코드def solution(numbers, hand): answer = '' keypad = {'1':(0,0), '2':(0,1), '3':(0,2), '4':(1,0), '5':(1,1), '6':(1,2), '7':(2,0), '8':(2,1), '9':(2,2), '*':(3,0), '0':(3,1), '#':(3,2)} left = keypad['*'] right = keypad['#'] for number in numbers: .. 2024. 9. 5.
[백준] 15686번 파이썬 - 치킨 배달 문제https://www.acmicpc.net/problem/15686코드from itertools import combinationsimport sysinput = sys.stdin.readlinen,m = map(int,input().split())city = []chicken = []house = []def CalculateDistance(chicken): value= 0 for i in house: nx,ny = i distance = int(1e9) for j in chicken: x,y = j distance = min(distance,abs(nx-x) + abs(ny-y)) value += d.. 2024. 8. 30.
[백준] 18405번 파이썬 - 경쟁적 전염 문제 코드from collections import dequeimport sysinput = sys.stdin.readlinen,k = map(int,input().split())array = []virus = []# 배열 초기화for i in range(n): array.append(list(map(int,input().split()))) for j in range(n): if array[i][j] != 0: virus.append((array[i][j],0,i,j))virus.sort()queue = deque(virus)# s초 후에 (x,y) 위치에 바이러스 s,x,y = map(int,input().split())# 상하좌우dx = [0,0,-1,1]d.. 2024. 8. 27.
[프로그래머스] 1844 C# - 게임 맵 최단거리 문제 c#으로 처음 알고리즘을 풀다 보니, 기본 문법 관련하여 모르는 것이 많아 어려움을 겪었다.문제 자체는 기본적인 BFS문제로 난이도가 높게 느껴지진 않았다. 코드using System;using System.Collections.Generic;public class Solution{ public int solution(int[,] maps) { int answer = 0; bool[,] visited = new bool[maps.GetLength(0), maps.GetLength(1)]; BFS(maps, visited, (0, 0)); if (maps[maps.GetLength(0) - 1, maps.GetLength(1) - 1] ==.. 2024. 8. 16.
[백준] 12015번 파이썬 - 가장 긴 증가하는 부분 수열 2 문제 첫 코드n = int(input())lst = list(map(int,input().split()))answer = 0dp = [1] * (n)for i in range(0,n): dp[i] = 1 tmp = 0 for j in range(i+1,n-i): if lst[i] tmp: tmp = lst[j] dp[i] += 1print(max(dp)) 다이나믹 프로그래밍을 사용하여 풀었고(LIS 알고리즘), 시간초과가 났다.문제 제목만 보고 입력 조건을 확인하지 않았다.. 위 코드의 시간복잡도를 계산해보니첫 for문에서 n, 두번째 for문에서 i부터 n까지 돈다고 해도결국 시간복잡도는 O(N^2)가 된다. 따라서 시간복잡도를 줄일.. 2024. 6. 27.
[백준] 1095번 파이썬 - 마법의 구슬 s+f개의 구슬 중 s개를 뽑는 조합의 개수를 구하고그 개수를 m이하의 사람들에게 모두 같은 개수로 나누어 주면 되는데이 때 m의 값이 최대여야 한다.첫 번째 코드# 1,000,000,000범위 -> 시간복잡도 O(N)import maths,f,m = map(int,input().split())answer = -1# 1. s+f개로 만들 수 있는 조합의 개수 구하기 -> math.comb 시간복잡도 O(logn)combs = math.comb(s+f,s)# 2. m 이하의 사람들이 모두 같은 개수의 조합을 테스트 할 수 있도록 나누기if combs 시간초과  두 번째 코드# 1,000,000,000범위 -> 시간복잡도 O(N)import sysimport mathinput = sys.stdin.readl.. 2024. 5. 10.
[프로그래머스] 178870 파이썬 - 연속된 부분 수열의 합 (투포인터 알고리즘) 문제 이름과 제한 사항 (sequence의 길이 투포인터 알고리즘이 생각났다. 투포인터 알고리즘?- 두 개의 점의 위치를 기록하면서 처리하는 알고리즘- 특정한 합을 가지는 부분 연속 수열 찾기와 같은 문제 & 정렬되어 있는 배열 문제에 대표적으로 사용됨- 시작점은 끝점보다 작거나 같다는 조건을 항상 만족해야 한다.- 시간복잡도는 O(N)         - 포인터가 N번 증가해야 알고리즘이 끝나므로 하나의 포인터의 시간복잡도는 O(N)      2 * O(N) = O(N) 이므로 합쳐도 시간복잡도는 O(N) 풀이1. start, end 각각 0으로 설정 & 두 포인터 사이의 값의 합 sumNum = sequence[start]으로 초기화    1-1. sumNum이 k보다 크거나 같으면 start += 1.. 2024. 4. 12.
[프로그래머스] 92334 파이썬 - 신고 결과 받기 각 유저가 받은 결과 메일의 수를 출력하면 되는 문제.신고한 모든 내용을 취합, 마지막에 한꺼번에 게시판 이용 정지를 시킨다는 조건 때문에 구현이 어렵진 않았다.시간복잡도는 report의 길이가 최대 200,000 이기 때문에 이중 포문을 사용하지만 않으면 통과였다. 풀이1. id_list에 있는 id를 key값으로 가지는 dictionary에 [id가 신고당한수, 신고한 id들]을 value로 넣는다.2. report를 돌며 신고한 id,신고당한 id를 변수 a,b에 저장한다.    2-1. 만약 dic[a]가 신고한 id들(dic[a][1])에 b가 존재하지 않는다면,            dic[a][1]에 b를 append하고 dic[b]가 신고당한 수에(dic[b][0])에 1을 더한다.3. di.. 2024. 4. 11.

티스토리툴바