Tiny Bunny
본문 바로가기
[BOJ #24482] 알고리즘 수업 - 깊이 우선 탐색 4 문제 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 만들어 지는 트리를 깊이 우선 탐색 트리라고 하자. 깊이 우선 탐색 트리에 있는 모든 노드의 깊이(depth)를 출력하자. 시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1로 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다. dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 v.. 2024. 3. 25.
[#02][BOJ #9663] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 수도코드 배운 코드 # 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수? = ans def dfs(n): # n : 행 번호 global ans # 종료 조건 : n == N if n == N: ans += 1 return for j in range(N): # 열, 대각선 모두 queen 이 없는 경우 go if v1[j] == v2[n + j] == v3[n - j] == 0: v1[j] = v2[n + j] .. 2024. 3. 22.
[BOJ #1713] 후보 추천하기 문제 월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.. 2024. 3. 21.
[BOJ #1991] 트리 순회 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로.. 2024. 3. 21.
[#01][BOJ #15649] N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 배운 코드 def dfs(n, lst): # 종료 조건(n에 관련) 처리 + 정답 처리 if n == M: # M개의 수열을 완성 ans.append(lst) return # 하부 단계(함수) 호출 for i in range(1, N + 1): if v[i] == 0: # 선택하지 않은 숫자인 경우 추가 v[i] = 1 dfs(n + 1, lst + [i]) v[i] = 0 N, M = map(.. 2024. 3. 19.
백트래킹 공부 시작 !! 이제 처음 한다는건 아니지만.. 전부터 언젠간 본격적으로 백트래킹 공부를 해야겠다고 생각하고 있었다. ㅎㅎ 그 시작이 오늘이었을 뿐 !! 오늘 백트래킹 배웠는데 진짜 너무 코드를 못짜겠어서, 구글링도 해보고 유튭도 뒤져보는데 유튭에 백트래킹 문풀 플리가 있어서 그걸 하루에 하나씩만이라도 하면 괜찮겠다는 생각이 들었다. 그래서 바로 시작. 백트래킹 공부는 우선 문제풀이 영상을 정독하면서 코드를 따라 쓰면서 이해하고, 그 뒤에 그 코드를 일절 보지 않고 혼자 풀어볼 것이다. 그걸 실패했다? 그럼 혼자 풀 수 있을 때까지 그걸 반복할거다. 그래서 게시글 올릴 때에는 문제 링크와 설명 들었던 해설 코드, 내가 혼자서 풀어낸 코드, 제출 결과 이렇게 올릴 예정이다! 그러면 오늘부터 백트 아자아자 화이팅이다!! 2024. 3. 19.
[SWEA #11891] 분할정복 - 병합정렬 문제알고리즘 교수님은 학생들에게 병합 정렬을 이용해 오름차순으로 정렬하는 과제를 내려고 한다.정렬 된 결과만으로는 실제로 병합 정렬을 적용했는지 알 수 없기 때문에 다음과 같은 제약을 주었다.N개의 정렬 대상을 가진 리스트 L을 분할할 때 L[0:N//2], L[N//2:N]으로 분할 한다.병합 과정에서 다음처럼 왼쪽 마지막 원소가 오른쪽 마지막 원소보다 큰 경우의 수를 출력한다.정렬이 끝난 리스트 L에서 L[N//2] 원소를 출력한다.알고리즘 교수님의 조건에 따라 병합 정렬을 수행하는 프로그램을 만드시오. 입력첫 줄에 테스트케이스의 수 T가 주어진다. 1다음 줄부터 테스트 케이스의 별로 정수의 개수 N이 주어지고, 다음 줄에 N개의 정수 ai가 주어진다.5i  출력각 줄마다 "#T" (T는 테스트 케이.. 2024. 3. 18.
[BOJ #18870] 좌표 압축 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 내가 쓴 코드 1 (시간 초과) from sys import stdin; input = stdin.readline N = int(input()) arr = list(map(int, input().. 2024. 3. 18.
728x90
반응형

티스토리툴바