썸네일 [프로그래머스] 옹알이(1) (Python, 문자열) 🌱 문제 https://school.programmers.co.kr/tryouts/85889/challenges 🌱 풀이 babbling의 단어가 "aya", "ye", "woo", "ma"로 완벽하게 만들어질 수 있어야 하므로 맨 앞부터 4개의 옹알이 중 하나라도 일치하는 것이 있는지 검사합니다. 검사하면서 4개의 옹알이 중 하나와 일치하는데, 남은 글자가 해당 옹알이의 글자 수와 일치한다면 babbling의 단어가 4개의 옹알이 단어들로 모두 만들어진다는 것을 의미하므로 answer를 1 증가시킵니다. 🌱 코드 # !/usr/bin/python3 # -*- coding: utf-8 -*- # programmers 옹알이 def solution(babblings): answer = 0 for babbl..
썸네일 [BOJ] #2437 저울 (Python, Greedy) 🌱 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 🌱 풀이 0. 접근하기 문제 예시에서 추가 1, 1, 2, 3, 6, 7, 30일 때, 정답이 21입니다. 이를 추의 배열이 [1, 1, 2, 3, 6, 7, 30]일 때 앞에서부터 차례대로 더한 값의 배열은 [1, 2, 4, 7, 13, 20, 50]입니다. 정답이 21임을 아는 상태에서는 1-20까지의 무게는 무조건 만들 수 있다고 판단할 수 있습니다. 이 때 1부터 20까지는 무조건 만들 수 있으므로 31부터 50까지도 무조건 만들 수 있음을 알 수 있습니다..
썸네일 [BOJ] #11000 강의실 배정 (Python, 우선순위 큐, 그리디) 🌱 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🌱 풀이 우선순위 큐 자료구조를 활용하여 푸는 그리디 문제입니다. 1. 시작 시간을 기준으로 정렬하기 class_times = [list(map(int, input().split())) for _ in range(n)] class_times.sort(key = lambda x: x[0]) 우선 순위 큐에 삽입 하기 이전에 우선, 입력 받은 강의 시간을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다. 그 이유는 아래 예시를 통해서 설명하도록 하겠습니다. 아래에서 정렬 없이 큐에 삽입한 경우, 첫 번째..
썸네일 [BOJ] #16724 피리 부는 사나이 🌱 문제 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 🌱 풀이 0. 기본 로직 safe_zone = [] idx = 1 for i in range(n): for j in range(m): if visited[i][j] == False: dfs(board, i, j, visited) idx += 1 방문하지 않은 노드를 돌면서 dfs 탐색을 합니다. dfs 함수에서 무조건 하나의 사이클이 찾아지므로 dfs함수를 수행하고 나오면 idx 값을 증가시킵니다. 1. dfs 함수 d..
썸네일 [BOJ] #1027 고층 건물(Bruteforce, Python) 🌱 문제 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 🌱 풀이 1. 기울기 계산 def calc_gradient(x1, y1, x2, y2): if x1 == x2: return 0 gradient = (y2 - y1) / (x2 - x1) return gradient 건물이 보이는지 여부는 기울기에 따라 결정되므로 기울기를 계산하는 함수를 작성합니다. 1. 완전탐색 (Bruteforce) results = [] for idx in range(len(buildings)): cnt = 0 min_gradie..
썸네일 [BOJ] #1450 냅색문제 (이분 탐색, Python) 🌱 문제 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 🌱 풀이 1. 기존 Bruteforce로 풀 수 없는 이유 이 문제는 물건의 개수(n)가 최대 30개 주어집니다. 만약 이 문제를 완전 탐색으로 푼다면 물건 하나하나마다 넣을지 안넣을지 모든 경우를 세면 최대 $2^{30}$번의 연산을 하게 되는데, 이는 10억이 넘는 값으로 무조건 시간 초과가 발생합니다. 기존 Bruteforce로 푼다면 코드가 다음과 같을 것입니다. import sys from itertools import combinations ..
썸네일 [BOJ] #2110 공유기 설치 (이분탐색, Python) 🌱 문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🌱 풀이 이 문제는 이분탐색 문제입니다. 이 문제에서는 집들 사이의 간격을 이분탐색하여 조정합니다. 아래에서 자세히 설명해보겠습니다. 0. 입력 받기 n, c = map(int, input().split()) position = [int(input()) for _ in range(n)] position.sort() 집의 개수 n과 공유기 개수 c를 입력 받습니다. 집의 위치를 리스트(position)에..
썸네일 [Programmers] 단어 변환 (Python, BFS) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. 해당 단어에서 바꿀 수 있는 단어 리스트 만들기 (그래프 만들기) BFS 탐색을 할 것이기 때문에 현재 위치(현재 단어)에서 갈 수 있는(한글자 바꿀 수 있는) 위치를 담은 리스트(노드간 연결 정보를 담은 그래프)를 만들어야 합니다. 예를 들어, 단어 리스트가 hot, dot, dog, log, log, cog일 때, 그래프에는 아래와 같이 저장되어야 합니다. # 해당 단어에서 갈 수 있는 단어 정보 저장 (그래프 만들기) for i in range(len(words)): word1 =..
썸네일 [Programmers] 네트워크(BFS/DFS 풀이 | Python) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 전형적인 DFS 알고리즘을 이용해서 푸는 문제입니다. 0. 변수 초기화와 그래프 정보 visited = [False for _ in range(n + 1)] graph = [[] for _ in range(n + 1)] answer = 0 for i in range(len(computers)): for idx, val in enumerate(computers[i]): if i != idx and val == 1: graph[i + 1].append(idx + 1) 인접 행렬 방식으로 주어진 ..
썸네일 [BOJ] #2252 줄 세우기 (Python) 🌱 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🌱 풀이 0. 입력 받기 n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] in_degree = defaultdict(int) for i in range(m): small, big = map(int, input().split()) graph[small].append(big) in_degree[big] += 1 학생수(n)과 키를 비교한 횟수..
썸네일 [BOJ] #1976 여행가자(Python) 🌱 문제 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🌱 풀이 0. 입력 받기 및 변수 초기화 n = int(input()) m = int(input()) graph = [] parent = [i for i in range(n + 1)] for i in range(n): graph.append([idx + 1 for idx, i in enumerate(list(map(int, input().split()))) if i == 1]) plan = list(map(int, input().split())) 전체 ..
썸네일 [BOJ] #13144 List of Unique Numbers (Python) 🌱 문제 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 🌱 풀이 0. 입력 받기 n = int(input().rstrip()) num_list = list(map(int, input().split())) 수열의 길이와 수열의 원소 값들을 입력받습니다. 1. 변수 초기화 result = 0 start, end = 0, 0 seq = [False] * 1000001 투포인터를 이용해 풀기 위해 num_list의 인덱스를 가리킬 start와 end를 각각 0으로 초기화 해줍니다. seq에 수열에 들어갈 수 있는 최댓값인 ..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바