전체 글

위상 정렬만 알면 날먹 가능한 문제이다 https://www.acmicpc.net/problem/2252 학생들을 줄 세워야 하는데 우선순위의 일부분이 m개 주어진다 이를 위상정렬 그래프로 생각하면 반드시 정점 a(학생1) 을 먼저 방문한 이후, 정점 b(학생2) 를 방문해야 한다 라는 순서가 된다. 위상정렬에서는 정점 b를 가기 위해서는 반드시 정점 a를 지나쳐야 하므로, 진입차수(indegree)가 1 증가하게 된다. # 위상 정렬 from collections import deque v, e = map(int, input().split()) indegree = [0]*(v+1) # 진입 차수 graph = [[] for _ in range(v+1)] for _ in range(e): a, b = m..

22년 3월 5일 토요일 1시 시험을 따끈따끈하게 보고 왔습니다 ! 정보처리기사 시험은 본 다음에 큐넷 홈페이지에서 당일 오후에 답이 공개 되어 미리 채점을 해 볼 수 있습니다 !! 정보처리기사 시험은 총 150분으로 진행되고 5과목으로 이루어져 있습니다 컴공과라면 전공시간 때 한번씩은 훑게 될 내용으로 이루어져 있고, 개인적으로 1 ~ 4 과목은 CS 상식으로 많이 커버 가능한 문제들이라면 마지막 5 단원은 좀 자잘한 암기할 거리가 많아서 시간을 조금 투자하는 것이 좋아보입니다 .. 특히 3단원 DB 문제들은 정말 학교 수업만 잘 들어도 괜찮았던 것 같군요 그리고 2단원도 코드 실행 결과 묻는 것들 나오는데 이런건 안외워도 되니깐 오히려 좋아.. 그래도 정보처리기사가 매주 있는 시험도 아니니 ㅠ 한방에..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 내가 바로 백트레킹이다 !!!! 하는 문제 dfs에서 경로에 현재 확인중인 array[nx][ny] 의 알파벳이 들어갈때 확인하고 다시 제거해서 원상복구한다 그러나 시간 초과가 났다... 또륵 괜히 level.5 문제가 아니다 ㅎ # 1987 알파벳 r, c = map(int, input().split()) array = [] for _ in range(r): array.append(inp..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net # 1197 최소 스패닝 트리 v, e = map(int, input().split()) edges = [] parent = [0]*(v+1) for i in range(1, v+1): parent[i] = i def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, ..

여기서 바로 5시간 이내 pcr 검사를 하고 영문 진단서까지 받을 수 있다 출국 전날 24시간이내 pcr증명서를 지참해야 한다는 미국 규정에 부합하다 !! 그리고 심지어 휴무일없이 주말에도 한다 !! 알아서 다행...

try except 문은 이럴때 사용한다 !! 라는 것을 알게되었다. 보통 입력값 갯수가 주어지는데 이문제에서는 안주어져서 어떻게 하나 싶었는데 파이썬에서는 EOF 에러를 잡을 수 있는 구문이 바로 except! except를 이용해서 예외적으로 오류를 처리할 수 있게 해준다. 그리고 풀이는 전위순회의 특성을 이용해서 풀었다 전위순회는 root -> left subtree -> right subtree 순서대로 순회한다. 즉, 1) root는 array[0] # 맨 앞의 원소가 루트노드 2) array를 쭉 확인하다가 처음으로 root보다 큰 값이 나오면 이것이 바로 right subtree의 첫번째 원소가 되므로, left와 right 서브트리의 경계값이 된다 이 두가지를 이용하여 postorder 함..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이진탐색의 시간 복잡도는 O(logN)으로 선형탐색 O(n) 을 사용할 때보다 시간을 단축할 수 있다 # 10815 숫자카드 n = int(input()) card = list(map(int, input().split())) m = int(input()) find = list(map(int, input().split())) card.sort() def bisect(l..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net bfs로 풀기 위해서, 100001개의 공간이 필요하다 이 개수는 문제에서 주어진 노드의 범위(0