썸네일 [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에 수열에 들어갈 수 있는 최댓값인 ..
썸네일 [BOJ] #18405 경쟁적 전염 (Python) 🌱 문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 🌱 풀이 0. 입력 받기 n, k = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input().split()))) s, x, y = map(int, input().split()) 첫째줄에 시험관의 크기(n)와 바이러스의 종류의 개수(k)를 입력받습니다. 다음 n개에 줄에 시험관의 정보를 입력받습니다. 마지막 줄에 시간(s..
썸네일 [BOJ] #2230 수 고르기 (Python) 🌱 문제 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 🌱 풀이 투 포인터 알고리즘을 이용해서 푸는 문제입니다. 핵심 아이디어는 두 포인터가 가리키는 값이 m이상일 때, result를 업데이트해 나가는 것입니다. 그리고 업데이트와 동시에 왼쪽 포인터를 하나 증가시킵니다. 차이가 더 줄여질 수 있는지 확인하기 위해서입니다. 두 포인터가 가리키는 값이 m미만이라면 오른쪽 포인터를 하나 증가시켜, 차이를 키워줍니다. 🌱 코드 # !/usr/bin/env python # -*- coding: u..
썸네일 [BOJ] #9935 문자열 폭발 (Python) 🌱 문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🌱 풀이 1. 입력 받기 str = deque(list((input().strip()))) bomb = list(input().strip()) 전체 문자열과 폭발 문자열을 입력으로 받습니다. 빠른 pop연산을 위해서 전체 문자열은 queue로 바꿔줍니다. 2. 변수 초기화 stack = [] stack은 결과값을 저장할 변수입니다. 3. 스택과 큐 사용 while str: ch = str.popleft() stack.append(ch) i..
썸네일 [BOJ] #2473 세 용액 (Python) 🌱 문제 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 🌱 풀이 [BOJ] #2470 두 용액 (python) 🌱 문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모 eunbin00.tistory.com 2470번 두 용액의 업그레이드 버전입니다. 문제는 같고 용액만 3개를 고르면 됩니다. 포인터가 추가적으로 하나 더 필요한데, 용액..
썸네일 [BOJ] #2470 두 용액 (Python) 🌱 문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🌱 풀이 이 문제는 투 포인터 알고리즘을 이용합니다. 투 포인터 알고리즘이란, 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 구하는 알고리즘입니다. 1. 입력받기 n = int(input()) liquid = sorted(list(map(int, input().split()))) 입력은 두 줄이 주어집니다. 첫째 줄에는 전체 용액의 수인 n을 입력받고, 둘째 줄에서는 용액의 특..
썸네일 [BOJ] #2178 미로 탐색 (BFS, Python) 0. 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. BFS 이 문제를 BFS로 풀어야 하는 이유는 BFS는 시작 지점에서 가까운 노드부터 탐색하기 때문입니다. 이 문제는 (1, 1)에서 출발하여 (N, M)의 위치까지 이동할 때 지나야 하는 최소의 칸 수를 구해야 하므로 BFS 알고리즘으로 풀어야 적절합니다. 1. 우선, (0, 0)을 큐에 넣고 방문 처리합니다. (현재 queue: (0, 0)) 2. 큐에서 (0, 0)을 빼고 (0, 0)에서 상하좌우로 움직일 수 있고 한번도 방문하지 않은 칸을 큐에 넣고 방문처리한 후, 그래..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바