전체 글 썸네일형 리스트형 [백준/BOJ] 백준 코딩 알고리즘 1260번 DFS와 BFS Python 그래프와 순회 풀이 해설 이 문제는 DFS와 BFS의 원리를 따라 구현하여, 그 방문 순서를 출력하는 기본적인 문제이다 DFS는 stack을 이용하여 전체를 탐색할 수 있도록 하고, BFS는 queue를 이용하여 전체를 탐색할 수 있도록 한다 DFS는 함수 호출 및 반환이 stack 자료구조에 기반하였기 때문에, 재귀호출을 사용함으로써 별도의 stack을 정의해서 사용하지 않는다. 반면에 BFS는 colletions 라이브러리의 deque 객체를 사용함으로써 queue를 구현해 활용한다. 이 때 그래프를 구현하는 방법에는 여러가지가 있는데 본 코드에서는 인접 리스트와 인접 행렬 중에 인접 리스트를 사용하였다 전체 코드 import sys from collections import defaultdict, deque de.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 2606번 바이러스 Python 그래프와 순회 본 문제는 1번 컴퓨터에서 시작했을 때 연결로 인해 감염이 발생하는 컴퓨터의 수를 구하는 문제이다 감염 == 방문 개념으로 생각하면 기본적인 DFS, BFS 문제로 접근하여 풀 수 있다 그에 따라 각 풀이는 아래와 같다 BFS를 이용하는 경우 while queue: front = queue.popleft() # queue의 가장 앞 원소 front 가져오기 connect_list = [i for i in coms[front]] # front와 연결된 컴퓨터 목록 가져오기 for c in connect_list: # 연결된 컴퓨터 목록에 대해서 방문한 적이 없다면 전파 if not visited[c]: visited[c] = True queue.append(c) BFS를 이용하는 경우 queue의 fron.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 2630번 색종이 만들기 Python 분할 정복 나의 풀이 이 문제는 재귀를 이용한 분할 정복으로 풀 수 있다 우선 파란색 종이냐, 하얀색 종이냐, 혹은 아직 더 잘라야하는 종이인가를 판별하는 알고리즘을 짜야한다 이를 구현하려면, 길이가 n일 때 너비가 n^2임을 고려하여, 너비 영역의 합이 n^2임을 확인한다 만약 n^2인 경우 파란색으로 칠해진 종이이며, 파랑 카운트를 1 올린다 만약 0인 경우 하얀색으로 칠해진 종이이며, 하양 카운트를 1 올린다 그 외의 경우에는 아직 섞여 있는 것이기 때문에 종이를 더 자르도록 탐색을 진행한다 그러면 어떻게 나누어서 탐색을 해야할까? 그에 대해서는 다음과 같이 정리할 수 있다 정사각형의 색종이가 있을 때, N/2를 통해서 중간 지점을 구하여 4분할을 할 수 있다 그리고 위 그림에서 노란색으로 동그라미 친 부분을.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 9251번 LCS Python 다이나믹 프로그래밍 나의 풀이 이 문제는 DP 원리를 사용해서 크게 두 가지 방식으로 나눠 풀 수 있다 첫 번째는 2차원 배열을 사용하는 방식이고 두 번째는 누적합을 사용하는 방식이다 2차원 배열은 구현 및 이해 측면에서 좀더 간단하지만 시간 복잡도와 메모리 사용량이 좀 더 크고 누적합 방식은 시간 복잡도와 메모리 사용량을 크게 줄일 수 있지만, 이해 측면에서 살짝 복잡하다 첫 번째 : 2차원 배열 2차원 배열을 사용하여 두 문자열의 중복 길이 여부를 저장한다 위 이미지 토대로 설명하자면, 알파 문자열과 베타 문자열을 비교한다 열을 따라 내려오면서 비교한다고 가정할 때, 알파 문자열의 문자와 베타 문자열의 문자가 동일하다면 -> 이전 문자열까지의 공통 길이 저장값에 1을 더하여 저장한다 구체적으로는 다음과 같다. dp[i].. 더보기 [백준/BOJ] 백준 코딩 알고리즘 10844번 쉬운 계단 수 Python 다이나믹 프로그래밍 나의 풀이 우선 자릿수 에 따라서 계단수가 어떻게 늘어나는지 그려볼 수 있다 그러면 각 자릿수 의 앞의 자리 수에 있는 값에 따라서 경우의 수가 1개 혹은 2개로 달라지는 것을 알 수 있다 이를 다시 정리해본다면 현재 자릿수의 값에 따라서 언제 등장하는지 나눌 수 있다 현재 자릿수 값이 0이라면, 앞의 자릿수가 1일 때만 등장할 수 있고 현재 자릿수 값이 9라면, 앞의 자릿수가 8일 때만 등장할 수 있다 그 외 현재 자릿수 값이 n (n=1~8)이라면, 앞의 자릿수가 n-1일 때 혹은 n+1일때 등장할 수 있다 그리고 이를 코드로 다시 정리한다면 아래와 같다 dp 배열은 2차원 배열로 구성되고 첫 번째 차원은 자리수 두 번째 차원은 어떤 수가 나왔는지를 의미한다 그리고 해당 위치에는 그 경우에 따른 경우.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 1912번 연속합 Python 다이나믹 프로그래밍 나의 풀이 이번 문제는 문제의 제목부터 힌트를 주고 있다고 느껴졌다 말 그대로 '연속합'이기 때문에 현재 포인터가 보고 있는 수 까지에 대해서 연속하는 합과 그렇지 않은 값 (현재값)을 비교하여 최대값을 저장하면 된다 이를 간단히 정리하면 다음과 같다 dp[i] = max(i까지의 연속합, 현재값 i) 둘 중에 큰 값이 dp 배열에 저장되며, i까지의 연속합이 크다면, dp[i - 1] 값에 i값이 더해진 값이 dp[i]에 저장되며 현재값 i가 더 크다면, dp[i]에는 i 값이 저장된다 -> 이 말은 지금까지 있던 수를 더하는 것보다, i가 더 크기 때문에 연속이 끊기는 경우를 의미한다. 이를 코드로 나타내면 다음과 같다 import sys input = sys.stdin.readline N = int.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 1904번 01타일 Python 다이나믹 프로그래밍 첫 번째 풀이 import math N = int(input()) res = [] for i in range((N // 2) + 1): if i == 0: res.append(1) else: res.append(math.comb(N - i, i)) print(sum(res) % 15746) 첫 번째 풀이에서는 수학적인 접근 방법을 사용했다 '00' 타일이 0, 1, 2, ... 개 일 때에 따라 몇 개의 경우의 수가 가능한지 math 라이브러리의 combination 함수를 사용하여 계산하였다 예) N = 5 '00' 타일이 0개일 때 → 1 '00' 타일이 1개일 때 → 5-1C1 → 4 '00' 타일이 2개일 때 → 5-2C2 → 3 총합 : 8 위 방법은 정답 자체는 맞으나, 시간초과로 인해서 문제.. 더보기 [백준/BOJ] 백준 코딩 알고리즘 2579번 계단 오르기 Python (다이나믹 프로그래밍) 첫 번째 풀이 (3%에서 틀렸습니다.. ㄱ-) import sys input = sys.stdin.readline N = int(input()) stairs = [0] * N dp = [0] * N for i in range(N): stairs[i] = int(input()) for i in range(N): if i == 0: dp[0] = stairs[0] elif i == 1: dp[1] = stairs[0] + stairs[1] elif i == 2: dp[2] = max(dp[1], max(stairs[0] + stairs[2], stairs[1], stairs[2])) elif i == 3: dp[i] = max(dp[i-1], max(dp[i-2] + stairs[i], dp[i-3] + s.. 더보기 이전 1 2 3 4 ··· 22 다음
