썸네일 [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)에서 상하좌우로 움직일 수 있고 한번도 방문하지 않은 칸을 큐에 넣고 방문처리한 후, 그래..
썸네일 [BOJ] #11401 이항계수3 (Python) 1. 문제 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 11401 이항계수 3번 문제는 이항계수를 계산하는 문제입니다. 이항계수는 ${n \choose c}= \frac{n!}{r!(n - r)!}$ 공식을 이용하여 구할 수 있습니다. 문제에서 요구하는 답은 이 값을 1,000,000,007로 나눈 나머지를 출력하는 것입니다. 따라서 n, r, n-r의 팩토리얼 값을 DP로 계산합니다. 하지만 메모리 초과를 막기 위해서 팩토리얼 값을 그대로 저장하지 않고, 10000007로 나눈 값으로 저장할 것입니다. 그런데 이때 이항계수..
썸네일 [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..
썸네일 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 #5397) 키로거 | Python 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 💡아이디어 스택으로 구현합니다. 키보드 입력 커서를 기준으로 왼쪽 스택과 오른쪽 스택을 만듭니다. 스택을 만든 후, 입력된 문자열을 돌면서 백스페이스와 화살표에 따라 left_stack과 right_stack에 적절한 push, pop을 해줍니다. 💡전체 코드 전체 코드는 아래와 같습니다. test_case = int(input()) for _ in range(test_case): left_stack = [] right_stack = [] data = i..
썸네일 BAEKJOON #1904) 01타일 | DP(다이나믹 프로그래밍) | Python 백준 #9461 파도반 수열 (파이썬) 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 💡 해보면서 패턴 찾기 붙일 수 있는 타일은 00과 1, 두 종류 밖에 없다. 따라서 n이 주어지면 (n-2) 길이 타일 앞 뒤에 00을 붙이거나 (n-1) 길이 타일 앞 뒤에 1을 붙이는 방법으로 n개의 길이를 만들 수 있다. n = 1일 때는 한 가지 경우 뿐이다. n = 2일 때는 00과 11 두 가지 경우이다. n = 3일 때는 n=1일 때의 방법에 00 타일을 붙이는 방법과 n=2일 때의 방법에 1 타일을 붙이는 방법이..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바