알고리즘216

• 

  [백준] 19237번: 어른 상어 - 파이썬(python) 나의 풀이 import copy import sys input = sys.stdin.readline n, m, k = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(n)] # 격자판 smell = [[[0, 0] for _ in range(n)] for _ in range(n)] shark_dir = [0] + list(map(int, input().split())) # 현재 상어 방향 dir_rank = [[]] # 상어의 방향별 우선순위 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for i in range(m): array = [] for j in range(4): array.ap.. 알고리즘/구현 2022. 10. 25.

• 

  [백준] 19236번: 청소년 상어 - 파이썬(python) 나의 풀이 from collections import deque import heapq import copy def move_fish(shark, fish) : for i in range(1,17) : # 1번~16번물고기까지 차례로 이동 x,y = fish[i][0],fish[i][1] if x==-1 or y==-1 : # 없어진 물고기 continue rotate = shark[x][y][1] # i번 물고기의 방향 for _ in range(8) : nx = x + dx[rotate%8] ny = y + dy[rotate%8] # 해당 방향의 다음 칸이 범위안이고, 빈칸이거나 물고기가 존재한다면 if 0 알고리즘/DFS, BFS 2022. 10. 24.

• 

  [백준] 16236번: 아기 상어 - 파이썬(python) 나의 풀이 from collections import deque n= int(input()) arr = [] now_x , now_y = -1, -1 # 아기 상어의 위치 length = 2 # 아기 상어의 크기 cnt = 0 # 아기 상어가 먹은 물고기 개수 time = 0 # 아기 상어가 물고기를 잡아먹는데 걸린 시간 m = 0 # 물고기 개수 for _ in range(n) : arr.append(list(map(int, input().split()))) for i in range(n) : for j in range(n) : if arr[i][j] == 9 : now_x = i now_y = j arr[i][j] = 0 elif arr[i][j] > 0 : m += 1 dx = [1,0,-1,0] .. 알고리즘/DFS, BFS 2022. 10. 24.

• 

  [백준] 3665번: 최종 순위 - 파이썬(python) 나의 풀이 from collections import deque T = int(input()) for _ in range(T): n = int(input()) graph = [[False]*(n+1) for _ in range(n+1)] last_year = list(map(int, input().split())) # 작년의 순위 indegree = [0] * (n+1) # 진입차수 for i in range(n): for j in range(i+1,n) : graph[last_year[i]][last_year[j]] = True indegree[last_year[j]] += 1 # j의 진입차수 1증가 m = int(input()) # 상대적인 등수가 바뀐 쌍의 수 for i in range(m) : .. 알고리즘/Graph 그래프 2022. 10. 21.

• 

  [벡준] 2887번: 행성 터널 - 파이썬(python) 틀린 풀이 import heapq def find_parent(parent, x) : if parent[x] != x : parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, i,j) : a = find_parent(parent, i) b = find_parent(parent, j) if a < b : parent[b] = a else : parent[a] = b N = int(input()) arr = [] q = [] parent = [i for i in range(N)] for _ in range(N) : x,y,z = map(int, input().split()) arr.append((x,y,z)) .. 알고리즘/Graph 그래프 2022. 10. 21.

• 

  [백준] 11404번: 플로이드 - 파이썬(python) 나의 풀이 n = int(input()) m = int(input()) dis = [[int(1e9)] * (n+1) for _ in range(n+1)] for i in range(n+1) : dis[i][i] = 0 # 자기 자신으로 가는 노선은 0 for _ in range(m) : a, b, c = map(int, input().split()) dis[a][b] = min(dis[a][b], c) # a도시에서 b도시로 가는 비용 저장 for k in range(1, n+1) : for i in range(1, n+1) : for j in range(1, n+1) : dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]) for i in range(1, n+1) .. 알고리즘/최단경로 2022. 10. 20.

• 

  [이코테] 편집거리 - 파이썬(python) 문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert) : 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 조건 두 문자열 A와 B가 한 줄에 하.. 알고리즘/동적프로그래밍(DP) 2022. 10. 20.

• 

  [백준] 18353번: 병사 배치하기 - 파이썬(python) 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 .. 알고리즘/동적프로그래밍(DP) 2022. 10. 19.

• [백준] 1932번: 정수 삼각형 - 파이썬(python) 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 예제 입력.. 알고리즘/동적프로그래밍(DP) 2022. 10. 19.

• [프로그래머스] 가사 검색 - 파이썬(python) 문제 설명 친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지.. 알고리즘/이분탐색 2022. 10. 18.

• [백준] 2110번: 공유기 설치 - 파이썬(python) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는.. 알고리즘/이분탐색 2022. 10. 18.

• 

  [프로그래머스] 실패율 - 파이썬(python) 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로.. 알고리즘/Sort 정렬 2022. 10. 12.