썸네일 [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)에서 상하좌우로 움직일 수 있고 한번도 방문하지 않은 칸을 큐에 넣고 방문처리한 후, 그래..
썸네일 [BAEKJOON] #1202) 보석 도둑 (그리디, 최소힙) 백준 1202 보석 도둑 파이썬 문제 풀이입니다. 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net # !/usr/bin/env python # -*- coding: utf-8 -*- # boj 1202 보석 도둑 import sys import heapq input = sys.stdin.readline n, k = map(int, input().split()) jewelries = [tuple(map(int, input().split())) for ..
썸네일 [BAEKJOON] #1543 문서 검색 백준 1543번 문서 검색 파이썬 문제 풀이입니다. 문자열을 전체를 훑으며 매칭되는 경우를 검사하는 문제입니다. 이 문제에서 단어와 문서의 일부가 같은지 검사해야 하는 최대 경우의 수는 len(document) - len(word) + 1번입니다. 하지만, 단어가 중복되어 등장하면 안되기 때문에 검사했을 때 단어가 일치하면 검색하는 단어의 길이만큼 건너뛰어서 검사하면 됩니다. 따라서 i에 검색하는 단어(word)의 길이를 더해줍니다. 일치하지 않으면 1만 증가시킵니다. 검사해야하는 최대 경우의 수까지 i가 도달하면 반복문을 멈추고 결과값을 출력합니다! # -*- coding: utf-8 -*- # boj 1743 문서 검색 import sys if __name__ == "__main__": documen..
썸네일 [프로그래머스] 두 큐의 합 같게 만들기 | 파이썬 덱과 리스트의 연산 속도 차이 | LV2, python, 2022 KAKAO TECH INTERNSHIP 프로그래머스의 '두 큐의 합 같게 만들기' 문제입니다. 두 큐의 합이 같아질 때까지 push, pop을 해야 하는 최소 연산 개수를 구하는 문제입니다. 합이 더 큰 큐에서 pop하여 더 작은 큐로 push 해주는 것을 두 큐의 합이 같아질 때까지 반복하면 됩니다. 이때, 연산 개수가 전체 숫자의 개수 * (3/2)가 넘어가면 결국 두 개의 큐가 원래 상태로 되돌아 오기 때문에 합을 절대로 같게 만들 수 없다는 의미입니다. 이 때는 -1을 리턴하고 같아질 때까지 push pop 연산을 하며 연산 횟수만 1씩 늘려가주면서 최종적으로 연산 횟수를 리턴해주면 됩니다. 알고리즘 자체는 간단한데, 계속 시간 초과가 났습니다. 처음에는 while문을 반복할 때마다 큐의 합을 sum() 함수로 계속 새로 계산해주었습니..
썸네일 BAEKJOON #4195) 친구 네트워크 | union-find | Python 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net union find 알고리즘을 이용해서 푸는 문제입니다. union-find에 관한 자세한 내용은 아래 글을 참고해주세요:) Union Find 알고리즘 | 개념과 Python 코드 구현 안녕하세요. 은넨입니다. 오늘은 백준의 친구 네트워크 문제를 풀면서 알게 된 union-find 알고리즘에 대해 글을 작성해보려 합니다. 📌 Union Find 알고리즘이란? Union Find 알고리즘은 서로소 집합(Di eunbin00.tistory.com 처음에..
썸네일 BAEKJOON #10930) SHA-256 | Python 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net 단순한 문제입니다. 주어진 문자열의 해시값만 출력하면 됩니다. 하지만 저는 2번 틀렸습니다. 그 이유는 sys 라이브러리의 stdin을 이용하면 줄바꿈까지 입력값으로 들어갑니다. 따라서 입력값이 아주 조금만 달라져도 해시값은 완전히 바뀌기 때문에 틀릴 수 밖에 없습니다. 따라서 stdin을 이용하려면 줄바꿈을 없애서 해쉬값을 만들던지, 느린 input()함수를 사용하던지 해야 합니다. 저는 그냥 input()함수를 사용하였습니다. hash값 생성을 위해서는 파이썬의 haslib 라이브러리를 이용합니다. hashlib.sha256..
썸네일 BAEKJOON #9461) 파도반 수열 | DP | Python 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 💡 점화식 $f(n) = f(n - 3) + f(n - 2)$ 💡 코드(python) import sys input = sys.stdin.readline def padovan(n): dp = [1] * (n + 1) dp[0] = 0 for idx in range(3, n + 1): dp[idx] = dp[idx-3] + dp[idx-2] return dp[n] if __name__ == "__main__": cnt = int(input()) for _ in rang..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바