조이의 개발 다이어리

[Python] 백준 16401 과자 나눠주기

1. 문제 - 백준 16401 과자 나눠주기https://www.acmicpc.net/problem/16401 💡알고리즘 - 이분탐색조카의 수 M (1 숫자의 크기가 굉장히 크다.과자의 길이가 N개 주어지고, 각 과자를 여러개 나눌 수 있다는 가정 하에 막대 과자의 최대 길이를 구한다 -> 원하는 타겟이 있다.숫자의 크기가 굉장히 큰 상황에서 특정 조건을 만족하는 값을 구해야하는 경우, 이분탐색을 활용한다.✅ 풀이m, n = map(int, input().split())arr = sorted(list(map(int, input().split()))) # 이분 탐색을 위해 과자의 길이를 정렬한다.start, end = 1, arr[-1] # 과자의 길이는 양수이므로 start를 1, end를 a..

[Python] 백준 3055 탈출

1. 문제 - 백준 3055 탈출https://www.acmicpc.net/problem/3055 💡알고리즘 - BFS인접한 칸으로 이동하며, 고슴도치가 비버의 굴로 이동하기 까지의 최소 시간을 구하는 문제이므로 BFS를 활용한다.일반 BFS와 다른 점은 고슴도치가 단순히 탐색하는 것이 아니라 아래 사항을 고려해야한다.1) 물도 같이 인접한 칸으로 흐름2) 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. ✅ 풀이물과 고슴도치가 동시에 인접한 칸으로 움직인다.고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.=> 물이 인접한 칸으로 차는 최소 시간을 먼저 기록한뒤..

1. 문제 - 백준 2665 미로 만들기https://www.acmicpc.net/problem/2665 💡알고리즘 - 0-1 BFS0-1 BFS란 가중치가 0, 1만 존재하는 그래프에서의 최단 거리를 구하는 알고리즘이다.가중치가 0인 경로를 우선적으로 탐색하기 위해 이 경우 deque에 appendleft하여 front에 두고, 가중치가 1인 경로는 가중치가 0인 경로보다 후순위이므로 deque에 append하여 back에 둔다.흰방으로 이동할때, 검은 방에서 흰 방으로 바꾸지 않아도 되므로 가중치 0검은 방으로 이동할 때, 검은 방에서 흰 방으로 바꾸어야 하므로 가중치 1로 두고 알고리즘을 짠다.자세한 알고리즘 설명 관련해서는 https://velog.io/@iamdudumon/0-1-BFS 참고 ..

1. 문제 - 백준 14890 경사로https://www.acmicpc.net/problem/14890 💡알고리즘 - 구현삼성SW역량테스트 문제이다. 문제의 조건에 맞게 구현 잘하면 되는 문제..!✅ 풀이n, l = map(int, input().split()) # l: 경사로의 길이, 갯수 무제한board = []for i in range(n): board.append(list(map(int, input().split())))answer = 0 # 경사로를 놓음으로서 길을 만들 수 있는지 판단하는 함수# 경사로를 놓은 곳에 또 경사로를 놓는 경우 -> False# 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 -> False# 낮은 지점의 칸의 높이가 모두 같지 않거나, L개 연속 X ..

1. 문제 - 백준 1018 체스판 다시 칠하기https://www.acmicpc.net/problem/1018 💡알고리즘 - 구현입력받은 보드에서 모든 8x8 크기의 체스판을 잘라 다시 칠해야하는 정사각형의 갯수를 구하는 문제이다.✅ 풀이import copyn, m = map(int, input().split()) # mxn 크기의 보드board = []for _ in range(n): board.append(list(input())) answer = int(1e9)def simulation(x, y, board): # 8x8 함수에서 칠해야하는 정사각형의 갯수 구하는 함수 # 처음이 B인지 W인지에 따라 칠해야하는 갯수가 달라진다. w_index=0 # W로 시작하는 보드에서 칠하는 갯수..

1. 문제 - 백준 1043 거짓말https://www.acmicpc.net/problem/1043 💡알고리즘 - 집합, 유니온-파인드 알고리즘문제의 조건을 정리해보면, 이야기의 진실을 아는 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.요약하면 이야기의 진실을 아는 사람, 이야기의 진실을 아는 사람에게 들은 사람이 없는 파티에서만 과장된 이야기를 할 수 없다.=> 파티의 사람들을 입력받을 때, 파티 인원들끼리 같은 집합으로 만들어(유니온 연산) 각 파티의 구성원 중 1명이라도 진실을 아는 사람의 집합의 구성..

1. 문제 - 백준 1941 소문난 칠공주https://www.acmicpc.net/problem/1941 💡알고리즘 - 조합 or 백트래킹, 그래프탐색(DFS/BFS)조합/백트래킹: 25명의 여학생들 중 7명의 여학생을 고른 모든 조합에 대해 조건을 만족하는 방안이 있는지 확인하므로 조합/백트래킹 활용 가능그래프탐색: 7명의 여학생들이 서로 인접해있는지, 이다솜파의 학생이 적어도 4명이상 포함되어있는지 등 확인하는 과정에서 그래프탐색 알고리즘 사용✅ 풀이from collections import dequeboard = []for _ in range(5): board.append(list(input()))visited = [[False] * 5 for _ in range(5)]answer = 0dx ..

1. 문제 - 백준 16954 움직이는 미로 탈출https://www.acmicpc.net/problem/16954 💡알고리즘 - BFS시작점(7,0)이 있고 도착점(0,7)이 있고 그래프 탐색이라는 점에서 DFS, BFS를 활용할 수 있다. 필자는 BFS가 더 편해서 BFS 사용✅ 풀이from collections import dequedx = [-1, 1, 0, 0, -1, -1, 1, 1, 0]dy = [0, 0, -1, 1, -1, 1, -1, 1, 0] # 인접한 한칸 혹은 대각선 방향, 현재 위치에 서있을 수 있음board = []for _ in range(8): board.append(list(input()))# board에서 벽 아래로 이동하는 함수 하나 필요def move_wall(..

1. 문제 - 백준 16139 인간-컴퓨터 상호작용https://www.acmicpc.net/problem/16139 💡알고리즘 - 구간합 알고리즘문자열의 구간 별 알파벳의 등장 횟수를 구해야하나, 문자열의 길이가 200,000자 인데 질문의 갯수인 q도 200,000개이다.매번 반복문을 통해 알파벳의 등장 횟수를 구하면 시간초과가 발생한다.구간 문제의 해답을 구할 때 O(N^2)의 시간복잡도를 O(N)의 시간복잡도로 해답을 구할 수 있도록 해주는 알고리즘이 구간합 알고리즘이다.구간합 알고리즘이란? i ~ j 구간합을 구할 때 누적합을 구해두고 -> arr[i] - arr[j-1] 의 공식을 통해 구간합을 구하는 방식이다.✅ 풀이import sysinput = sys.stdin.readlineexamp..

1. 문제 - 백준 17141 연구소 2https://www.acmicpc.net/problem/17141 💡알고리즘 - BFS, 브루트포스바이러스를 놓을 수 있는 위치에 m개의 바이러스를 넣은 모든 경우의 수 중 바이러스를 퍼뜨릴 수 있는 최소 시간을 반환한다 -> 브루트포스상하좌우 인접한 빈칸으로 복제되며, 바이러스를 퍼뜨리는 최소 시간 -> BFSfrom collections import dequefrom itertools import combinationsimport copy# 모든 빈 칸에 바이러스를 퍼뜨리는 최소시간 -> BFS# 바이러스를 놓을 수 있는 칸들에 m개의 바이러스를 놓기 -> 조합, 완전탐색n, m = map(int, input().split())board = []dx = [-..