나의 개발일지

문제 : https://www.acmicpc.net/problem/1417 그리디, 최대 힙 사용 from heapq import heapify n = int(input()) dasom = int(input()) heap = [-int(input()) for _ in range(n-1)] # 최대 힙 구현을 위해 -를 붙여 저장 cnt = 0 heapify(heap) if n == 1: print(0) exit() while dasom

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/87946 완전 탐색 모듈 itertools 의 permutations(순열) 를 사용해서 풀이 순열이란 n개 중 서로다른 r개를 선택하고 순서를 고려하는 것을 말한다. from itertools import permutations def solution(k, dungeons): all = [i for i in permutations(dungeons,len(dungeons))] # 순열 구하기 ok = [] # 조합별로 탐험 횟수 담을 리스트 for i in range(len(all)): fatigue = k # 피로도 count = 0 # 탐험 횟수 for j in all[i]: if fat..

문제 : https://www.acmicpc.net/problem/1068 DFS 부모 노드를 지우면 자식 노드로 갈 길이 없어지기 때문에 제거해야 할 노드만 지우면 자식 노드들을 다 지울 필요 없다. import sys from collections import defaultdict input = sys.stdin.readline tree = defaultdict(list) n = int(input()) nodes = list(map(int, input().split())) remove_node = int(input()) for i in range(n): if i != remove_node: # 제거해야 할 노드 제외하고 추가 tree[nodes[i]].append(i) if remove_node in..

문제 : https://www.acmicpc.net/problem/11724 DFS 파이썬으로 풀이 할 경우 재귀 깊이 한계가 정해져 있어 새롭게 지정 필요 sys.setrecursionlimit(10**9) from collections import defaultdict import sys sys.setrecursionlimit(10**9) # 재귀 깊이 한계 지정 input = sys.stdin.readline n, m = map(int, input().split()) # 정점, 간선 graph = defaultdict(list) for i in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) visit ..

문제 : https://www.acmicpc.net/problem/26169 dfs, 백트레킹 Map = [list(map(int, input().split())) for _ in range(5)] r, c = map(int, input().split()) # 행, 열 visit = [[0] * 5 for _ in range(5)] visit[r][c] = 1 mx, my = [1, -1, 0, 0], [0, 0, 1, -1] def dfs(r, c, d, apple): # 행, 열, 깊이, 사과 갯수 if d > 3: # 4번 이동하면 돌아가 return if apple >= 2: # 사과 2개 먹었으면 나가 print(1) exit() for i in range(4): # 상하좌우 네 방향 탐색 nx..

문제 : https://www.acmicpc.net/problem/1388 전체 타일의 개수 n*m에서 연결된 타일의 수를 빼주었다. n, m = map(int, input().split()) lst = [list(input()) for _ in range(n)] answer = n * m for i in range(n): for j in range(m): if j != m-1 and lst[i][j] == "-" and lst[i][j+1] == "-": answer -= 1 if i != n-1 and lst[i][j] == "|" and lst[i+1][j] == "|": answer -= 1 print(answer)

문제 : https://www.acmicpc.net/problem/16173 BFS 한 칸씩 이동이 아닌 현재 위치에 적혀있는 숫자만큼 이동을 시키는 문제 (오른쪽, 아래로만) from collections import deque n = int(input()) Map = [list(map(int, input().split())) for _ in range(n)] visit = [[0] * n for _ in range(n)] visit[0][0] = 1 q = deque([(0, 0)]) while q: x, y = q.popleft() mx, my = [0, Map[x][y]], [Map[x][y], 0] # 현재 위치에 적힌 숫자만큼 이동 if x == n-1 and y == n-1: print("H..

조합 공식 : https://terms.naver.com/entry.naver?docId=3350149&cid=60210&categoryId=60210 n개 중 서로 다른 r개를 선택하되 순서를 고려하지 않는 것을 말한다. 코드 구현 def factorial(a): n = 1 for i in range(2, a+1): n = n * i return n n, r = map(int, input().split()) # n, r 둘 중 더 큰값을 n의 자리에 넣는다. result = factorial(n) // (factorial(r) * factorial(n - r)) print(result) 순열 공식 : https://terms.naver.com/entry.naver?docId=3350148&cid=602..