DFS / Union Find 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 그래프에서 cycle이 존재하면 해당 그래프는 트리가 될 수 없다. 즉, 해당 문제는 어떠한 그래프가 주어졌을 때 cycle이 존재하는지의 여부를 구하고 트리의 갯수를 세는 문제이다. 이 문제는 union find나 dfs를 사용해서 풀 수 있다. 나는 이 문제를 총 2가지 방식으로 풀어보았다. (1) Union Find 이용 사실 이 문제는 ..

백트래킹 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net (1) 처음에 생각한 방식 import sys import heapq n, m = map(int,sys.stdin.readline().split()) graph = [] home = [] chicken = [] for i in range(n): l = list(map(int,sys.stdin.readline().split())) for j in range(n):..

DFS + Memorization 문제 (DFS로만 풀 시 시간초과) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net (1) 시간초과난 코드 (실패) # 내리막 길 (골드 3) / DFS-recursion (시간 초과) import sys r, c = map(int, sys.stdin.readline().split()) arr = [] visit = [[False] * c for _ in range(r)] dx = [-1, 0, 1, 0] dy = ..

Dijkstra 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net (1) 처음에 실패한 이유 (1) 처음엔 distance[start] = 0 이부분을 빼뜨려서 dijkstra 로직이 동작하지 못했다. 즉, distance 벡터를 출력했을 때 값이 모두 최댓값으로 나오는 문제가 있었다. [10001, 10001, 10001, 10001, 10001] 이런식으로 나왔었음. (2) 두번째로는 distance..

BFS 문제 (1) 처음에 내가 생각한 방식 #BFS from collections import deque import math a,b=map(int,input().split()) queue = deque() count=[] ans=0 queue.append(a) index=0 while queue: index+=1 q = queue.popleft() if q==b: ans=math.ceil(math.sqrt(index)) break queue.append(q*2) queue.append(int(str(q)+str("1"))) print(ans) 처음에 이 문제를 보자마자 나는 위와 같은 방식으로 풀었다. 하지만, 예제 입력 1이나 예제 입력 3처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 ..

(1) 처음 내 코드 -> 시간초과a,b = map(int,input().split())cnt = 0s1="4"s2="7"for i in range(a,b+1): s = str(i) bool=True for j in s: if j==s1 or j==s2: continue else: bool=False break if bool==True: cnt+=1print(cnt)입력이 1보다 크고, 1,000,000,000보다 작거나 같은 자연수로, 코드 제출하기 버튼을 누르면서도 뭔가 시간초과가 날거 같았다.  (2) 문제 해결 후 내 코드 -> product 사용from itertools impo..