알고리즘65 [BOJ] 1027. 고층 건물 문제https://www.acmicpc.net/problem/1027빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다.i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 빌딩이 보이는 고층 빌딩에서, 볼 수 있는 빌딩의 최대값 출력하라 주요 아이디어단순 길이비교 문제가 아님에 유의할 것직선의 경사를 통해 풀이하는 문제target의 오른쪽에 위치한 빌딩들의 경우, 이전 건물들보다 기울기가 크면 됨target의 왼쪽에 위치한 빌딩들의 경우, 이전 건물들보다 기울기가 작으면 됨 코드 구현 (Python 3.. 2024. 6. 25. [BOJ] 5427. 불 문제https://www.acmicpc.net/problem/5427동서남북으로 퍼져나감벽에는 불 X -> 불이 옮겨진 칸 / 불이 붙으려는 칸으로 이동 X상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있음얼마나 빨리 빌딩 탈출 가능한가? 주요 아이디어상근이가 맵 밖으로 나가는 게 종료 조건각 경로마다 불이 붙는 시간을 기록하고 상근이가 지나갈 수 있는 시간인지 판단 코드 구현 (Python 3)from collections import dequedef fire(): global w, h, graph, direction queue = deque() fire_time = [[-1 for _ in range(w)] for _ in range(h)] # 초기 불 위치.. 2024. 6. 25. [BOJ] 1181. 단어 정렬 문제https://www.acmicpc.net/problem/1181길이가 짧은 것부터길이가 같으면 사전 순으로 정렬단 중복 단어는 제거 주요 아이디어cmp_to_key 라이브러리에 사용자 정렬 조건을 전달해 풀었다 코드 구현 (Python 3)from functools import cmp_to_keydef compare(w1, w2): if len(w1) len(w2): return 1 else: if w1 제출 결과 2024. 6. 25. [프로그래머스] 무지의 먹방 라이브 문제https://school.programmers.co.kr/learn/courses/30/lessons/428911번 음식부터 오름차순으로 1초씩 음식을 먹음K초 후 몇 번 음식을 먹고 있는가?더 섭취할 음식이 없다면 -1 반환하기 주요 아이디어{음식번호 : 소요시간} 딕셔너리 형태로 저장오름차순으로 돌려가며 하나씩 빼주고, K초 후를 계산해준다 코드 구현 (Python 3)def solution(food_times, k): answer = 0 # dict 추가 food_dict = {} for idx, time in enumerate(food_times): food_dict[idx] = time idx = 0 # k번 반복 wh.. 2024. 6. 25. [BOJ] 10026. 적록색약 문제https://www.acmicpc.net/problem/10026N*N 크기의 그리드 각 칸에 RGB 중 하나를 색칠한 그림그림은 몇 개의 구역으로 나뉘는 데 구역은 같은 색으로 이뤄져있음같은 색상이 인접한 경우 두 글자는 같은 구역 = 같은 영역 주요 아이디어DFS 문제라고 하는데 BFS로도 풀 수 있을 것 같아서 이걸로 풀었다!BFS로 인접 노드를 순회하면서, 색깔 같을 때마다 방문하고 queue 순회를 끝내면 +1 (구역 추가)대신 적록색약과 정상인의 기준을 다르게 해주어야 하므로, flag 변수를 통해 구분을 주었다 코드 구현 (Python 3)더보기 from collections import dequen = int(input())graph = [[x for x in input()] fo.. 2024. 6. 25. [BOJ] 1351. 무한 수열 문제https://www.acmicpc.net/problem/1351이것도 처음에 뭔 말이지..? 싶었다현재 인덱스를 P와 Q로 나눈 것의 "내림값" 인덱스의 합A_0 = 1 주요 아이디어전형적인 DP 문제탑다운 방식으로 풀어보자! 코드 구현 (Python 3)더보기 from collections import defaultdict# 수열 n번째 반환def dp(n): # 저장되어 있는 값이면 if data[n] != 0: return data[n] data[n] = dp(n // p) + dp(n // q) return data[n]n, p, q = map(int, input().split())data = defaultdict(int)data[0] = 1 # 초기값 작.. 2024. 6. 25. 이전 1 2 3 4 ··· 11 다음
