개발자 퉁이리

https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr ⊙ 문제 ⊙ 제한사항 ⊙ 입출력 예 ⊙ 입출력 예 설명 ⊙ 문제 접근 과정 백트래킹으로 풀자! 계속해서 양의 수와 늑대의 수를 비교! 같아지는 순간 return. 아니라면 다음 노드를..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 자기 자신을 선택하면 혼자 팀을 구성할 수 있고, 원을 이루어 모든 사람이 선택되면 모든 학생들이 동일한 팀을 꾸릴 수 있다. 즉, 조건은 사이클이다. 사이클이 생기면 팀이 생기는데 사이클 판별을 dfs로 해주었다. ⊙ 문제 풀이 import sys sys.setrecursionli..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌려서 그림의 총 개수와 가장 넓은 그림을 찾아내면 된다. bfs를 돌릴 때, 내장 count는 그림의 넓이다. 그 값과 기존에 저장된 큰 그림의 넓이와 비교해서 더 큰 값을 max에 저장해준다. 이때 방문을 했는지 안 했는지 알기 위해 visited 리스트..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌렸다. 2번. 한 번은 입력받은 RGB 그대로 돌려서 구역을 찾아냈다. 마지막 한번은 R을 전부 G로 바꾸고 visited 여부를 초기화해준 후 돌려줬다. ⊙ 문제 풀이 import sys from collections import deque ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 백트래킹 ⊙ 문제 접근 과정 bfs를 사용해 문제를 풀었다. 조건을 통해 알파벳이 탐색하지 않았고 범위 안에 있다면 탐색을 추가한다. 계속해서 반복하여 answer의 최댓값을 갱신해준다. 처음에 dfs로 문제를 풀어봤는데 pypy로 해도 시간 초과가 나서 bfs로 풀었다. ⊙ 문제 풀이 i..

https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 비트마스킹 백트래킹 플로이드-와샬 외판원 순회 문제 ⊙ 문제 접근 과정 플로이드 와샬을 이용하여 모든 행성 방문 시 최단거리를 구하는 문제이다. 플로이드 와샬에선 문제없이 풀었지만, dfs 구현하는 부분에서 어려움을 느껴 어흥님의 블로그에서 해당 문제의 dfs 부분을 참고했다. 자세한 건 코드 주석에 적어놨다! ⊙ 문제..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 DFS를 이용하여 백트래킹을 했다. 재귀를 통해 순열을 구하기 위해 DFS를 통해 문제를 접근했는데 방법과 개념만 잡혀있으면 구현하기가 비교적 간단하다고 생각한다. 어렵다. 어려워( + 2021.08.10 내용 추가 ) 무슨 오만인지 예전에 적었을 때, 쉽다고 적었을까. 다시 백트래킹을 보는데 생각보다 더 ..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 단순 트리의 부모만 구하면 되는 문제다. DFS, BFS 두 가지 풀이 방법이 있는데 DFS로 풀어봤다. vector에 값을 대칭으로 입력한다. 그리고 자식노드에 하나씩 방문하여 부모를 지정해주는 로직으로 풀었다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 BFS 문제이다. 시작 값을 bfs() 함수에 넣고 방문할 때마다 값을 하나씩 올려준다. 그리고 마지막에 목표값에 대해 출력하면 된다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 102..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 다른 bfs와 비슷하지만 이번에는 대각선까지 고려해주어야 한다. 상, 하, 좌, 우, 우상, 우하, 좌하, 좌상. 총 8개의 방향을 탐색해 방문 체크해주었다. 그리고 reset() 함수를 직접 만들어주어 결괏값을 출력하면 계속 리셋해주고 반복해주었다. ⊙ ..