본문 바로가기

알고리즘

 (305)
[백준] 11779번 : 최소비용 구하기2 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🤔 문제분석 우선순위큐를 이용하여 문제를 해결하였는데요, 예전에 풀었던 유형이랑 비슷해서 문제를 쉽게 풀 수 있었습니다. 방문 경로를 구하는 로직은 거꾸로 우선순위큐를 역추적 하면됩니다. 말로는 어렵지만 코드를 보면 쉽게 이해 할 수 있습니다. 💻 코드 import sys import heapq input = sys.stdin.readline INF = sys.maxsize n = int(input..
[백준] 12851번 : 숨바꼭질 2 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 문제분석 너비우선탐색으로 문제를 해결하였는데 처음 방문한경우와 이전위치에서 오는 경우 두가지를 따져서 모든 경우의 수를 구해야합니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) vistied = [-1] * 100001 queue = deque() qu..
[백준] 1600번 : 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🤔 문제분석 너비우선탐색과 방문배열을 K차원으로 두어 문제를 해결하였습니다. 너비우선탐색을 하게되면 x,y좌표에서 i번 움직였을때가 가장 최소거리임으로 3차원 배열을 만듭니다. 시작점으로부터 원숭이가 이동하는 방법과 말과 이동하는 방법 모두 탐색합니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline K = int(input()) W..
[백준] 20056번 : 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 🤔 문제분석 문제의 포인트는 1번행과 N번행이 연결되어있고, N번열과 1번열이 연결되어있는 상태를 어떻게 구현할 것인가가 이 문제의 포인트 입니다. chage_dir 함수를 만들었고 해당 함수는 음수가 되든 범위가 넘어가든 상황을 나머지 연산을 활용하여 처리하였습니다. 파이어볼이 여러개 모여있는곳을 딕셔너리를 활용하여 딕셔너리에 리스트를 받고 리스트가 2보다 클경우 파이어볼을 분산시킵니다..
[백준] 1022번 : 소용돌이 예쁘게 출력하기 1022번: 소용돌이 예쁘게 출력하기 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 🤔 문제분석 회전하는 로직을 구현하는것이 이문제의 핵심이다. 회전은 아래의 사진과 같이 이루어진다. i가 (2, 3, 4, 5 … ) 1씩 증가하면서 두번씩 (좌 or 우), (상 or 하) 움직인다. 그것을 방향은 방향을 다움직이고나서 다음 방향으로 전환 시켜주면 된다. 회전 구현이 다 끝났다면 이제 문제에 조건이 맞는 길이를 맞추어주면 끝 💻 코드 import sys input = sys.stdin.readline r1, c1, r2, c2 = map(int, input().split()) R = r2 - r1 + 1 C = c2 - c1 ..
[백준] 2931번 : 가스관 2931번: 가스관 2931번: 가스관 www.acmicpc.net 🤔 문제분석 너비우선탐색으로 파이프 다음에 빈칸이 나올경우를 구한뒤 그 빈칸이 어떤 파이프가 들어가야하고, 그 파이프가 들어갔을때 기존에 있던 파이프와 호환되는지 확인해서 찾으면 된다. 파이브가 호환되는지 판단하는 로직은 네 방향을 모두 방문 해보면서 그 해당하는 파이프가 그 방향으로 열려있는 파이프를 찾고, 그 방향으로 가르키는 파이프를 추론합니다. 추론하는 방식은 딕셔너리와 배열의 인덱스를 활용하여 찾아내었습니다. 💻 코드 import sys input = sys.stdin.readline from collections import deque pipe_type = ['|','-','+','1','2','3','4'] moves = [..
[백준] 1036번 : 36진수 1036번: 36진수 1036번: 36진수 첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 🤔 문제분석 파이썬에서 36진수로 변환해주는 기능이 있어서 더욱 쉽게 풀 수 있었습니다. 자리수와 알파벳을 고려한 가중치를 모두 구하고 가중치가 가장 높은 수를 K개 선택하여서 K개를 모두 Z로 바꿔준 후 모든 문자열의 10진수로 변환하여 모두 더한 뒤 다시 36진수 자리로 변환합니다. 💻 코드 import sys from collections import defaultdict VALUE_36 = "0123456789ABCDEFGH..
[백준] 18809번 : Gaaaaaaaaaarden 18809번: Gaaaaaaaaaarden 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 🤔 문제분석 파이썬의 조합 라이브러리를 활용하여 초록색 씨앗과 빨간색 씨앗 후보를 모두 부르트포스 하여 문제를 해결하였습니다. 초록색 씨앗과 빨간색 씨앗의 후보가 생성되었다면, 씨앗을 퍼트려야합니다. 너비우선탐색을 활용하였습니다. 너비 우선 탐색을 활용한 이유는 너비우선탐색은 최단거리 탐색을 우선으로 탐색하기때문에 초록색 씨앗과 빨간색 씨앗이 동시에 접하는 부분을..

티스토리툴바