Sujin's Log Sujin's Log

문제 링크https://www.acmicpc.net/problem/1753 힙큐힙큐는 우선순위 큐라고도 하는데, 제일 작은 수를 제일 먼저 pop 할 수 있도록 해주는 큐이다. 그래서 항상 pop을 하면 제일 작은 수가 먼저 pop이 되기 때문에 greedy 탐욕적이라고 불리기도 한다. 다익스트라 알고리즘 이용 문제 우선 이 문제에서 사용하는 그래프는 단방향 그래프이기 때문에 V, E = map(int, input().split())K = int(input())graph = [[] for _ in range(V + 1)]for _ in range(E): u, v, w = map(int, input().split()) graph[u].append((v, w))그래프는 이런식으로 코드를 구현하였..

문제 링크 https://www.acmicpc.net/problem/7569 이분 그래프(Bipartite Graph)의 정의- 정점을 두 그룹으로 나눌 수 있는 그래프- 이분 그래프가 될 수 있는 조건: 같은 그룹 안에는 간선이 없어야함- 즉 모든 간선은 다르 그룹을 연결 예시그룹 1: {A, B} 그룹 2: {C, D} 간선: A-C, A-D, B-C, B-D → 가능 ✅간선: A-B → A와 B가 같은 그룹 → ❌bfs 이용 문제- is_bipartite 함수에서 전체 for 문을 도는 이유: 그래프가 연결 그래프가 아닐 수도 있기 때문에 - bfs 구현 코드- 인접 노드들을 모두 돌면서 아직 방문하지 않은 노드인 경우 현재 노드의 반대 색깔을 적용- 만약 방문한 노드인데 현재 노드와 색이 같은 경..

문제 링크 https://www.acmicpc.net/problem/7569 bfs(그중에서도 멀티소스 bfs) 이용 문제1. 시작이 맨 첫번째 인덱스에서가 아님-> 3중 for문을 돌며 익은 토마토를 모두 큐에 삽입 2. 큐를 돌며 익은 토마토의 아래 위 왼쪽 오른쪽 앞 뒤를 현재 익은 토마토 값 + 1 을 해서 넣어줌 -> 최소 일수를 구하는 핵심 포인트이 값이 최소 일수를 의미 3. 큐 요소들이 모두 소진되면 3중 for문을 통해 그래프를 돌며 모든 토마토가 익었는지 답이 무엇인지 확인함- 여기서 max를 통해 일수를 찾는데 왜 최소 일수를 찾으면서 최대 일수를 구하나 라는 의문이 생길 수 있음가장 늦게 익은 토마토가 익은 날짜를 알아야함 구현 코드from collections import dequ..

문제 링크https://www.acmicpc.net/problem/2206 BFS 이용 문제1. q에 넣는 정보: y, x, , 지금까지 온 거리 2. 현재 인덱스에서 dy, dx 변수를 이용하여 상하좌우를 이동하며,다음에 q에 넣어줄 인덱스(y, x)가 배열의 인덱스 범위를 벗어나지 않는지 확인 3. 벽이 아니고 아직 방문하지 않은 경우 / 벽이고 아직 벽을 부순적이 없는 경우로 나누어 q에 삽입 -> 벽인데 이미 벽을 한 번 부순적이 있는 경우는 자동으로 중단됨 4. 답을 return y, x가 n-1, m-1에 도달했을 경우 dist 변수 returnwhile문이 종료되었는데 dist가 return 되지 않은 경우-> 0, 0에서 n-1, m-1로 가는 경로가 존재하지 않으니 -1 return ..

문제 링크https://www.acmicpc.net/problem/1967 트리의 지름 알고리즘 구현1. 아무 노드에서 시작해서 가장 먼 노드를 찾는다. (DFS 이용) 여기서는 1- 예를 들어서 1번 노드에서 DFS/BFS 를 돌려서 가장 먼 노드를 찾고, 그게9라고 하자- 이때 9번 노드는 트리의 한쪽 끝(leaf)임 2. 가장 먼 노드 9에서 다시한번 DFS9에서 가장 먼 노드를 찾으면 그게 다른 쪽 끝 노드임 -> 지름 의미 트리의 특징을 이용 -> 어떤 노드에서 가장 멀리 있는 노드는 항상 지름의 양 끝 중 하나가 된다. 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinen = int(input())graph = [[] for ..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 동적계획법(Dynamic Programming) 이용 문제 1. 점화식 의미 정의dp[i]: N을 정확히 i번 사용하여 만들 수 있는 모든 수들의 집합 2. dp 초기화N을 한 번 사용하면 표현할 수 있는 수는 N뿐 dp[1] = {N} 3. 반복구성 i = 2 ~ 8dp[i]에 숫자를 이어붙인 값 int(str(N) * i)을 추가1~i까지 j 변수를 통해 돌면서 dp[j]와 dp[i-j]를 이용해 + , -, *, // 사칙연산 i 반복문..

BFS(Breadth First Search, 너비 우선 탐색)이 알고리즘의 핵심은 큐(Queue)를 사용하는 것노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보를 큐에 넣어 큐에 먼저 들어있던 노드부터 방문.list 형식을 사용해 큐를 구현할 수도 있지만, list.pop(0)은 시간복잡도가 O(N)이므로 비효율적. -> collections 라이브러리의 deque를 사용. 방문하지 않았던 노드를 큐에 넣을때는 set타입을 사용. DFS(Depth First Search, 깊이 우선 탐색)이 알고리즘의 핵심은 스택(Stack)을 사용하는 것.

문제 1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다. 2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다. 메모이제이션을 사용하지 않은 구현 import java.util.Scanner; public class Section7_4_Ver1 { public static int DFS(int n) { if (n == 1 || n == 2) return 1; else return DFS(n - 2) + DFS(n - 1); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scann..