오늘은 여기까지

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 사용개념: 다익스트라  일반적인 다익스트라 문제다. 주의할 점이라면 무방향/양방향 그래프라는 점, 그리고 두 마을을 연결하는 도로가 여러 개일 수 있다는 점이다.   전체 코드import java.util.*;class Solution { static class Node implements Comparable { int vertex, weight; public Node(..

https://www.acmicpc.net/problem/1753사용개념: 다익스트라  다익스트라를 통해 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.최단거리를 저장하는 배열과 우선순위 큐를 이용해 구현한다.  전체 코드import java.io.*;import java.util.*;public class Main { static class Node implements Comparable { int vertex, weight; public Node(int vertex, int weight) { this.vertex = vertex; this.weight = weight; } @Override ..

https://www.acmicpc.net/problem/1916사용개념: 다익스트라 가중치를 갖는 그래프에서 최단 경로를 찾는 문제이므로 다익스트라 알고리즘을 사용해 해결한다. 그래프 입력 받기graph = [[] for _ in range(N+1)]for _ in range(M): start, end, cost = map(int, input().split()) graph[start].append((end, cost)) 입력 결과)[[], [(2, 2), (3, 3), (4, 1), (5, 10)], [(4, 2)], [(4, 1), (5, 1)], [(5, 3)], []] 다익스트라 알고리즘def dijkstra(graph, start): # 모든 노드의 거리를 무한대로 초기화 ..

https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  효율성 테스트 통과X. linked list로 다시 풀어볼것~def solution(n, k, cmd): table = list(range(n)) deleted = ['O'] * n stack = [] current = k for c in cmd: if c[0] == 'U': current -= int(c[2:]) elif c[..

https://www.acmicpc.net/problem/5212 원 지도는 탐색용으로 그대로 두고, 50년 후 지도를 그리기 위해 new_map을 deepcopy한다.지도 전체를 돌면서 땅이 나오면 상,하,좌,우를 확인한다.주변이 `"."` 이거나, 지도 범위를 벗어난 경우 모두 바다로 취급하여 cnt를 증가 시킨다.주변의 세 칸 이상이 바다라면 땅이 잠긴다.지도 크기를 최소화한다.육지('X')를 포함하는 가장 작은 직사각형 영역만을 남기기 위해, 남아있는 땅의 가장 왼쪽, 오른쪽, 위, 아래 좌표를 찾는다.해당 범위 내의 지도만을 결과로 출력한다.전체 코드import copydef find_map(R, C, map): new_map = copy.deepcopy(map) dx = [1, -1..

https://www.acmicpc.net/problem/10157사용개념: 그리디 1. 시간복잡도최악의 경우 모든 좌석을 방문해야 하므로 O(C*R)이다. 5 ≤ C, R ≤ 1,000 이므로 시간 내 계산 가능하다.  2. 풀이2차원 배열에서 나선형 패턴으로 좌석을 배정한다. 방향 벡터를 사용하여 위, 오른쪽, 아래, 왼쪽 순서로 이동한다. 배열의 범위를 벗어나거나 이미 방문한 위치를 만나면 방향을 바꾼다. def find_seat(C, R, K): if K > C * R: return 0 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] seats = [[0] * C for _ in range(R)] x, y = 0, 0 directi..

https://www.acmicpc.net/problem/19941사용개념: 그리디  1. 최적 해 구하는 법?왼쪽 사람부터 좌,우에 존재하는 K거리 이내의 햄버거 중 가장 좌측의 것을 먹는것이 모든 사람이 가장 많은 햄버거를 먹을 수 있는 방법이다.따라서 그리디 알고리즘을 사용한다.  2. 시간 복잡도최대 N명의 사람마다 인접한 K개의 원소를 탐색해야 한다. 그러므로 시간복잡도는 O(N) * O(K)가 된다. N은 최대 20,000개, K는 최대 10개로 약 200,000개의 연산은 시간 내에 가능하다.  전체 코드n, k = map(int, input().split())positions = list(input())answer = 0for i in range(n): if positions[i] =..

사용개념: 브루트포스, 완전탐색 1. 완전 탐색이 가능한지?K는 최대 9이므로 최악의 경우 숫자를 뽑는 경우의 수가 10!(=3628800)개 생긴다. 이는 시간 제한 안에 충분히 탐색 가능하다.2. 전체 코드from itertools import permutationsk = int(input())signs = list(input().split())number = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]numbers = list(permutations(number, k+1))def check(num): flag = True for i in range(k): sign = signs.pop(0) if sign == " num[i+1]: ..

https://www.acmicpc.net/problem/14247 사용개념: 그리디  1. 최적해 구하는 방법?현재 키와 성장률을 기준으로 각각 생각해본다.당장 제일 키가 큰 나무를 선택한다 (X)성장률이 작은 나무부터 선택한다 (O)모든 나무는 최대 n일 동안 성장할 수 있다. 따라서 나무마다 하루 성장하고 잘릴 수도, n일 동안 성장하고 잘릴 수도 있다.그렇기 때문에 하루에 성장할 수 있는 길이가 가장 긴 나무를 제일 마지막에 자르는게 최대로 나무를 자를 수 있는 방법이다.성장률이 제일 큰 나무만 계속 자르면 안되나?다른 나무들의 초기 길이를 자를 수 없다. 2. 나무를 성장률에 따라 정렬하기# 나무를 성장률에 따라 정렬trees = []for i in range(n): trees.append..

https://www.acmicpc.net/problem/2210사용개념: 브루트포스, 그래프 탐색, dfs재귀를 통해 dfs 그래프 탐색 구현숫자의 길이가 6이 되면 리턴한다.4가지 방향에 대해 그래프를 탐색한다.다음 탐색 위치가 그래프 범위를 벗어나지 않는지 확인한다.벗어나지 않는다면 재귀함수로 다시 호출한다. 이때까지 구한 숫자에 새로 탐색하여 얻은 수를 이어 붙인다.결과를 set에 저장하여 중복을 피한다.편의상 문자열로 숫자를 표현한다.def dfs(x, y, number): if len(number) == 6: result.add(int(number)) return for i in range(4): nx = x + dx[i] n..