CS/Algorithm 문제
[BaekJoon] 백준 17471번 게리맨더링
[BaekJoon] 백준 17471번 게리맨더링 🎈문제 https://www.acmicpc.net/problem/17471 💬설명 2 ≤ N ≤ 10 , 1 ≤ 구역의 인구 수 ≤ 100 제한사항이 위와 같아 0.5초에도 충분이 돌릴 수 있는 양이라고 생각했기 때문에 조합 -> bfs를 이용해 풀어줬다. 문제 풀이 순서 1-N/2만큼의 조합을 구한다. (ex. N=4일때, 길이 1 + 길이 3, 길이 2 + 길이 2의 조합) 구한 조합을 가지고 각각에 대해, 총 2번 bfs를 돌린다. bfs를 돌았을 때 모든 노드가 2개의 선거구로 나뉠 수 있다면(연결되어 있다면) 인구수 차이의 최소값을 update한다. 👩💻코드 # BaekJoon17471.py from collections import deque ..
[BaekJoon] 백준 1949번 우수마을
[BaekJoon] 백준 1949번 우수마을 🎈문제 https://www.acmicpc.net/problem/1949 💬설명 이차원 배열로 dp를 짜는건 아직 어려운 것 같다ㅜ dfs + dp로 풀어주면 되는 문제 파이썬에서는 재귀 함수 깊이에 제한이 있어서 sys.setrecursionlimit()을 통해 이를 풀어줘야 한다. 👩💻코드 # BaekJoon 1949.py import sys sys.setrecursionlimit(20000) N = int(input()) people = [0] + list(map(int, input().split())) visited = [False for _ in range(N + 1)] # 방문여부 저장 s = [[] for _ in range(N + 1)] # 연..
[BaekJoon] 백준 2352번 반도체 설계
[BaekJoon] 백준 2352번 반도체 설계 🎈문제 https://www.acmicpc.net/problem/2352 💬설명 LIS 문제인데 DP로 풀게되면 시간초과가 난다. 이분탐색으로 문제를 풀어줘야 한다. 👩💻코드 # BaekJoon 2352.py N = int(input()) arr = list(map(int, input().split())) lst = [] # 이분 탐색으로 lower bound 찾아주기 def find(s, e, v): global lst while s < e: m = (s + e) // 2 if lst[m] < v: s = m + 1 else: e = m return e for i in range(N): # 첫번째 숫자인 경우 if i == 0: lst.append(ar..
[BaekJoon] 백준 17144번 미세먼지 안녕!
[BaekJoon] 백준 17144번 미세먼지 안녕! 🎈문제 https://www.acmicpc.net/problem/17144 💬설명 - 단순한 구현문제였다. - 다만 python3로 채점하니 시간초과가 나서 pypy로 채점했다. 👩💻코드 # BaekJoon17144.py import copy # 변수 및 배열 초기화 R, C, T = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] A = [[] for _ in range(R)] cleaner = [] for i in range(R): A[i] = list(map(int, input().split())) for _ in range(T): # 확산 new_A = copy.deepcopy..
[BaekJoon] 백준 2098번 외판원 순회
[BaekJoon] 백준 2098번 외판원 순회 🎈문제 https://www.acmicpc.net/problem/2098 💬설명 간단하게 말하자면, 해당 문제는 사이클을 구하는데 그 사이클을 돌 때 가장 적은 비용이 드는 사이클을 구하는 것이다. 즉, 1->0->2->3->1 이렇게 돌아서 오는 경우와 2->3->1->0->2 이렇게 돌아서 오는 경우가 드는 비용이 같다는 것을 우선 염두에 두고 생각을 해보자. (편의상 0번 도시부터 있다고 가정하자.) 그렇게 되면, 우리는 모든 경우를 돌 때 0번 도시에서 출발한다고 가정해도 무방하다. 0->...->0 에서 ("..." 에 들어가는 도시들의 순서 + 모든 도시들을 돌았는지)만 고려해주면 되니까! 다시 말해서, 0번 도시에서 시작하는 경우만 생각하더라도..
[BaekJoon] 백준 2668번 숫자고르기
[BaekJoon] 백준 2668번 숫자고르기 문제: https://www.acmicpc.net/problem/2668 내코드 - 문제의 규칙을 찾아보면 다음과 같다. - 사이클을 이루는 값이면 결과에 포함된다. 따라서 다음과 같이 풀었다. - 1-N까지 반복을 돈다. - 각 i번에 대해 i번에서 시작해서 dfs를 돌았을 때 이미 처음에 방문했던 i번으로 다시 돌아오게 된다면 사이클을 이루는 경우고 결과에 포함된다. - 마지막에 sort를 해주지 않아 틀렸었다. # BaekJoon2668.py N = int(input()) arr = [[] for _ in range(N + 1)] result = set([]) for i in range(N): tmp = int(input()) arr[tmp].appen..
[BaekJoon] 백준 16234번 인구 이동
[BaekJoon] 백준 16234번 인구 이동 문제: https://www.acmicpc.net/problem/16234 내코드 - 우선 특정 조건을 만족하는 경우 인접한 모든 행을 탐색한다는 점에서 그래프의 탐색문제라고 생각했다. - dfs, bfs 어느것으로 풀어도 상관없지만 시간, 메모리 효율성이 dfs가 낫다는 말이 생각나 dfs를 선택했다. - 조건만 잘 따진다면 간단하게 풀리지만 python으로 채점하니 시간초과가 나서 pypy3로 채점했다. # Baekjoon16234.py import sys input = sys.stdin.readline N, L, R = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] arr = [0 f..
[BaekJoon] 백준 1915번 가장 큰 정사각형
[BaekJoon] 백준 -번 문제이름 문제: https://www.acmicpc.net/problem/1915 내코드 - 점화식을 생각해내기 약간 까다로운 dp문제였다. - 점화식은 다음과 같다. - dp[i][j] = [i][j]칸을 정사각형의 가장 오른쪽 아래라고 했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이 - dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 - 왜 위의 점화식이 성립하는지는 그림을 그려보면 쉽게 알 수 있다. import java.io.*; import java.util.StringTokenizer; public class test { public static void main(String[] args) throws ..