본문 바로가기

알고리즘/백준

 (263)
[백준] 17136번 : 색종이 붙이기 17136번: 색종이 붙이기 해당문제는 완전탐색 + 그리디로 문제를 해결 할 수 있습니다. 색종이의 종류는 5가지 이고 각각의 색종이를 붙혀보면서 모두 붙힐 수 있는 경우중 최소 개수를 카운팅 합니다. 특정 좌표에서 붙힐 수 있는 색종이의 크기 구하기 최대 색종이의 크기를 구한뒤 해당위치에서 모두 색종이를 붙혀본다. 색종이를 모두 붙혔다가 때면서 10*10의 크기의 종이위에 다 붙일 수 있는지 판별한다. import sys sys.setrecursionlimit(10**6) table = [] for _ in range(10): temp = list(map(int, input().split())) table.append(temp) remain = [5 for _ in range(6)] def check(..
[백준] 1300번 : K번째 수 1300번: K번째 수 해당 문제는 이분탐색문제로 문제의 정답을 찾는데에 고민이 많았다. 문제의 핵심은 K번째 수를 구해야하는 것이고, 숫자의 규칙을 잘 파악하여 K번째수가 몇인지 찾아야한다. 배열의 크기가 매우 크기때문에 메모리에 넣고 정렬을 하여 구하는 알고리즘은 바람직 하지 않다. 문제 풀이의 아이디어는 다음과 같습니다 특정한 숫자를 정하고, a[i][j]를 모두 순회하면서 자기자신보다 큰 값을 찾습니다. 샌 개수가 많다는것은 값이 더 커야 다음에 순회하였을때 개수가 줄어들 것이고, 샌 갯수가 적다는것은 자기자신의 숫자를 낮추어야 갯수가 작아지므로 이분으로 범위를 좁혀가며 정답을 찾습니다. 여기서 더 시간복잡도를 줄일 수 있는 방법은 나누기 연산을 수행하는것입니다. 예를들어 i가 1일때 j 1,2,..
[백준] 14890번 - 경사로 14890번: 경사로 해당 문제는 완전탐색 문제로 문제에 주어진 조건에 맞게 모두 탐색을 해보아 경우의 수를 구하면 된다. 길을 지나갈 수 있으려면 모든 칸의 높이가 같아야한다. 높이가 다른경우 경사로를 놓아서 길을 만들 수 있다. 경사로의 높이는 항상 1이며, 길이는 L이다. 경사로를 놓을 낮은칸의 높이는 모두 같아야하고, L개의 연속되어 있어야한다. 따라서 다음과 같은 조건으로 문제를 해결할 수 있다. 이전위치와 현재위치의 높이 차이는 반드시 1이어야한다. 현재위치 높이 > 이전위치 높이 : 이전에 있던 위치들이 길이가 L이어야한다. 또한 중복 경사로 만들기 불가 현재위치 높이 < 이전위치 높이 : 현재위치 다음에 있는 위치들의 길이가 L이어야한다. 중복 경사로를 만들기는 불가한 경우는 이전에 경사로..
[백준] 13460번 : 구슬 탈출2 13460번: 구슬 탈출 2 해당문제는 구슬 탈출 게임 보드를 동서남북으로 기울 였을때 빨간색 구슬을 꺼내는 게임이다. 완전탐색 및 구현으로 문제를 해결 할 수 있습니다. 동서남북으로 기울이는 함수를 작성하고, 여기서 주의 해야할것은 빨간색 구슬과 파란색 구슬이 동시에 움직일 수 있는 경우를 생각하여 구현을 해야한다. 예를들어 빨간색이 파란색구슬보다 한칸 바로 왼쪽 옆에 있을경우 왼쪽으로 기울이기를 했을때 빨간색 구슬과 파란색 구슬이 어떠한 상태가 될 것인지를 잘 생각해보고 문제를 해결해야한다. 모든 경우의수를 이제 기울어보면서 빨간색 구슬이 빠지는 지 확인하면 된다. 동시에 움직이는 경우를 생각하여 BFS 탐색으로 문제를 해결하였습니다. 빨간색 구슬이 먼저 이동해야 하는경우 queue에 먼저 넣어서 먼..
[백준] 17135번 : 캐슬 디펜스 17135번: 캐슬 디펜스 궁수 3명을 모든 경우의수로 위치에 배치해보면서 적을 죽일 수 있는 최대수를 구현하면 된다. 한명의 궁수에서 적을 죽일때 가장 거리가 가까운적이어야하고, 가까운 적이 여러명이라면 가장 왼쪽에 있는 적을 공격한다. 궁수가 죽일 수 있는 적은 가장 가까운 거리 이어야함으로 BFS 탐색을 하여 가장 가까운 최단경로의 적을 구한다. 적을 다 구했으면 적의 가장 가까운적중에서 x좌표가 가장 작은 적을 찾아서 죽인다. 💡 BFS + DFS로 문제를 해결하였습니다. DFS로는 궁수의 조합을 구하고, BFS로는 궁수가 공격할 수 있는 적을 구하였습니다. import sys from collections import deque from copy import deepcopy moves = [(-..
[백준] 15684번 - 사다리 조작 15684번: 사다리 조작 해당 문제는 완전탐색 문제로 놓을 수 있는 모든 사다리를 놓아보면서 사다리를 연결 했을때, 자기자신이 연결되는지 확인하는 백트래킹 + 완전탐색 + 구현 문제이다. 사다리를 놓을때에는 연속해서 놓이지 않게 해야하며 자기자신이 연결되는지 확인하는 구현, 추가해야하는 사다리의 개수가 넘어가면 백트래킹 하면 된다. 가능한 사다리를 놓아보는 조합을 구현하는것이 제일 복잡 했습니다. import sys input = sys.stdin.readline N, M, H = map(int, input().split()) sa = [[False for _ in range(H+1)] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().s..
[백준] 17835번 : 면접보는 승범이네 17835번: 면접보는 승범이네 해당 문제는 데이크스트라로 문제를 해결 할 수 있습니다. “면접장 까지의 거리”란 그 도시에서 도달 가능한 가장 가까운 면접장 까지의 최단 거리를 뜻한다. 가장 멀리에서 오는 면접자의 거리를 구해야한다. 모든 도시에서 면접장까지 모두 데이크스트라를 이용하여 i번째 도시에서 j번째의 면접장 까지 최단 거리를 구한뒤 거기서 최대 거리를 구해야 할까요?! 💡 반대로 생각하여 면접장에서 도시까지 방문해 보는것을 생각해보자. 각각의 면접장에서 동시에 출발하여 각각의 도시까지의 최단거리를 구하면 문제를 해결 할 수 있다. BFS의 특성을 잘이해 해야 한다. import sys import heapq from pprint import pprint input = sys.stdin.rea..
[백준] 20055번 : 컨베이어 벨트 위의 로봇 20055번: 컨베이어 벨트 위의 로봇 해당 문제는 기능별로 함수를 구현하여 문제를 쉽게 디버깅하고 풀어 나갈 수 있다. 밸트를 자료구조에 남아서 해당 문제를 해결 할 수 있다. 가장 먼저 벨트 위에 올라간 로봇을, 벨트가 회전하는 방향으로 한칸 이동할 수 있다면 이동한다. 이 방법에서 시간을 많이 빼았겼는데 1번 위치는 로봇을 올리는 곳이고, N번의 위치는 로봇을 내리는 위치이기때문에 로봇은 N-1의 위치에 있는곳에 로봇이 있다면 이 로봇이 가장 먼저 컨베이어 벨트에 올라간 로봇이다. from collections import deque N, K = map(int, input().split()) zerocount = 0 def rotate(table, robotvisited): num = table.p..

티스토리툴바