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 반복문..

Numpy수치적인 연산에 최적화된 파이썬 도구이다. 개발자는 파이썬 문법을 이용해 사용하지만 내부적으로는 C언어로 엄청난 최적화가 되어있어 더 효율적인 메모리 관리와더 효율적인 연산이 가능하도록 알고리즘 설계가 되어있다. 또한 컴퓨터 하드웨어를 효율적으로 활용한다는 장점이 있다. 예를 들어, 한국의 년도별 gdp가 달러로 표현된 배열을 원화로 환산하고싶다면, Python만 이용for i in range(len(gdp_korea_array)): gdp_korea_array[i] = gdp_korea_array[i] * 1335gdp_korea_array 파이썬에서는 배열 안의 모든 요소에 곱하기를 하고 싶을 때 이렇게 for문을 사용해서 하나하나 넣어주어야 하지만,numpy 이용gdp_korea_ar..

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