[Algorithm] DFS와 BFS 이 글은 이것이 코딩 테스트다(나동빈, 한빛미디어)을 읽고 공부한 내용을 바탕으로 정리한 글입니다. 오늘은 탐색 알고리즘 중 DFS와 BFS에 대해 공부해보겠습니다. 0. 그래프 자료구조 DFS와 BFS 모두 그래프 자료구조에서 자료를 탐색하는 알고리즘입니다. 그래프 자료구조에 대한 간단한 용어와 개념은 아래 글을 통해 보실 수 있습니다. Data Structure (5) Graph (그래프) 📌그래프란 : 실제 세계의 현상이나 사물을 정점(Vertex)(또는 노드(Node))와 간선(Edge)로 표현하기 위해 사용 📌용어 노드 Node: =정점(Vertex),그래프에서의 위치, 간선 Edge: 노드들을 연결한 선. 위치 eunbin00.tistory.com 그래프는 자료구조는 크게 2가지 방식으로 표현.. [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.. [프로그래머스] 두 큐의 합 같게 만들기 | 파이썬 덱과 리스트의 연산 속도 차이 | LV2, python, 2022 KAKAO TECH INTERNSHIP 프로그래머스의 '두 큐의 합 같게 만들기' 문제입니다. 두 큐의 합이 같아질 때까지 push, pop을 해야 하는 최소 연산 개수를 구하는 문제입니다. 합이 더 큰 큐에서 pop하여 더 작은 큐로 push 해주는 것을 두 큐의 합이 같아질 때까지 반복하면 됩니다. 이때, 연산 개수가 전체 숫자의 개수 * (3/2)가 넘어가면 결국 두 개의 큐가 원래 상태로 되돌아 오기 때문에 합을 절대로 같게 만들 수 없다는 의미입니다. 이 때는 -1을 리턴하고 같아질 때까지 push pop 연산을 하며 연산 횟수만 1씩 늘려가주면서 최종적으로 연산 횟수를 리턴해주면 됩니다. 알고리즘 자체는 간단한데, 계속 시간 초과가 났습니다. 처음에는 while문을 반복할 때마다 큐의 합을 sum() 함수로 계속 새로 계산해주었습니.. Union Find 알고리즘 | 개념과 Python 코드 구현 안녕하세요. 오늘은 백준의 친구 네트워크 문제를 풀면서 알게 된 union-find 알고리즘에 대해 글을 작성해보려 합니다. 📌 Union Find 알고리즘이란? Union Find 알고리즘은 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘입니다. 집합을 표현하는 자료구조로 배열, 연결 리스트 등을 활용할 수 있겠지만, 트리 구조가 집합 표현에서는 가장 효율적입니다. 따라서 Union set 알고리즘도 트리 구조를 사용하는 그래프 알고리즘으로 볼 수 있습니다. 서로소 집합은 서로 중복되지 않는 부분 집합을 의미합니다. 예를 들어, {1, 2}와 {2, 3}은 2라는 중복되는 원소가 있으므로 서로소 집합이 아니지만, {1, 2}와 {3, 4}는 서로 중복되는 원소가 없으므로 서로소 집합.. 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 타일을 붙이는 방법이.. 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.. BAEKJOON #11726) 2xn 타일링 | DP | Python 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 0️⃣ 초기화 이 문제를 풀기 위해서는 2x1 타일링 방법 개수와 2x2 타일링 방법 개수를 초기화하고 시작합니다. 2x1을 타일링하는 방법은 아래의 방법으로 1개 입니다. 2x2를 타일링하는 방법은 아래 방법으로 2개 입니다. 1️⃣ 2x3 타일 생각해보기 초기화 한 후, 2x3 타일링은 2x1타일링에 1x2타일 2개를 붙이고, 2x2타일링에 2x1타일 1개를 붙이면 됩니다. 2️⃣ 2x4 타일 생각해보기 2x4 타일 또한 앞의 방법처럼 2x2 타일에 1x2 타일 2개를 붙이고, 2.. 다이나믹 프로그래밍(DP, Dynamic Programming) 오늘은 다이나믹 프로그래밍에 대해서 공부해보겠습니다. 1학기 때에 산업공학 전공 수업인 경영과학에서 다이나믹 프로그래밍 방법을 이용해서 최적화 문제들을 풀었었는데 매우 재미있게 공부했습니다v_v 다이나믹 프로그래밍이 무엇인지 차근차근 알아봅시다. 💡 다이나믹 프로그래밍이란? DP란 입력 크기가 작은 부분 문제들의 해를 이용해서, 큰 부분의 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘을 말합니다. 상향식Bottom-up 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 그 값으로 상위 문제를 풀어가는 방식으로 memoization 기법을 이용합니다. memoization 기법이란, 주어진 입력값에 대한 결과를 저장해 놓음으로써 같은 입력값이 또다시 들어왔을 때, 저장해놓은 값을 사용하여.. 이전 1 2 3 4 5 6 7 8 다음
