EunJng

문제 백준 2470번 두 용액 | 골드5 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 알고리즘 분류: 정렬 | 이분 탐색 | 투 포인터 풀이 과정 파이썬 풀이 import sys input = sys.stdin.readline n = int(input()) lst = sorted(list(map(int, input().split()))) a, b = 0, 0 value = 2000000000 i = 0 j ..

문제 백준 1068번 트리 | 골드5 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 알고리즘 분류: 그래프 이론 | 그래프 탐색 | 트리 | 깊이 우선 탐색 풀이 과정 파이썬 풀이 import sys input = sys.stdin.readline def dfs(x): lst[x] = -2 for i in child[x]: # 자식 중 제거되지 않은 노드에 대해 재귀 if lst[i] != -2: dfs(i) n = int(input()..

문제 백준 1976번 여행 가자 | 골드4 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 알고리즘 분류 : 자료 구조 | 그래프 이론 | 그래프 탐색 | 분리 집합 풀이 과정 파이썬 풀이 - BFS와 유니온 파인드의 풀이 방법 순서 union find에 대한 설명은 아래 글에서 확인할 수 있습니다. https://eunjng.tistory.com/102 [Algorithm] Union Find Union Find 상호 배타적으로 이루어진 집합..

문제 백준 7569번 토마토 | 골드5 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 알고리즘 분류 : 그래프 | 너비 우선 탐색(BFS) 풀이 과정 자바 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; ..

문제 백준 17144번 미세먼지 안녕! | 골드4 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 알고리즘 분류: 구현 | 시뮬레이션 풀이 과정 전반적인 풀이 방법 설명 후, 파이썬과 자바 순서로 작성되어 있습니다. 풀이 방법 우선 공기청정기가 두 칸이므로 그 중 윗칸의 좌표를 air로 저장하고, 미세먼지가 움직이는 좌표들을 저장하기 위해 move라는 배열을 만들었다. 미세먼지가 확산되는 과정을 spread 함수를 통해 구현하였다. 이때 기존..

문제 백준 11054번 가장 긴 바이토닉 부분 수열 | 골드4 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 알고리즘 분류 : 다이나믹 프로그래밍(dp) 풀이 과정 파이썬 풀이 import sys input = sys.stdin.readline n = int(input()) nums = list(map(int, input().split())) inc = [1 for _ in range(n)] dec = [1 for _ in range(n)] for i in ra..

문제 백준 10026번 적록색약 | 골드5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 알고리즘 분류 : 그래프 | 너비 우선 탐색(BFS) | 깊이 우선 탐색(DFS) 풀이 과정 해당 문제의 파이썬 풀이는 아래 글 참조 https://eunjng.tistory.com/33 [BOJ] 10026 적록색약 | Python 문제 백준 10026번 적록색약 | 골드5 https://www.acmicpc.net/problem/10026 10..

문제 백준 1167번 트리의 지름 | 골드2 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 알고리즘 분류 : 그래프 | 트리 | 깊이 우선 탐색(dfs) 풀이 과정 파이썬 풀이 from collections import deque import sys input = sys.stdin.readline v = int(input()) tree = [[] for _ in range(v+1)] for _ in range(v): nums ..