본문 바로가기

Algorithm/BOJ

 (95)
[BOJ] 15650. N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택 (방문여부 확인해야함) - 재귀함수에서 M개를 선택할 경우 print - [1, 2], [2, 1] 속성이 같은 경우에는 중복을 제거해야하므로 재귀 시작 범위를 +1씩 2. 시간복잡도 - N! : 가능 (문제의 N이 자연수 8까지) 3. 자료구조 - 방문 여부 : bool[][] - 선택한 값 입력 배열..
[BOJ] 15649. N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 해결방법 """ ### 백트래킹 ### - 1부터 N중에 하나를 선택. - 다음 1부터 N을 선책할 때 이미 선택한 값이 아닌경우를 선택 > 방문여부 - M개를 선택할 경우 프린트 - 중복이 가능한 경우 : N^N : N = 8까지 가능 - 중복이 불가능한 경우 : N! : N = 10까지 가능 - 시간복잡도가 2억이 넘지 않아야 한다. (1초에 2억개 연산 python) 1. 아이디어 -..
[BOJ] 2602. 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 그래프 배열에서 a vertex에 b vertex를 append 시킨다. - BFS 돌면서 다녀간 vertex는 방문기록 배열로 처리한다. - BFS를 돌면서 감염된 컴퓨터의 수를 구한다. 2. 시간복잡도 - O(n^2) : 100^2 X M 3. 자료구조 - 2차원 배열 : int[][], bool[][] - BFS : Queue """ 2. 정답코드 입력 예제..
[BOJ] 1260. DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 공통 : 방문기록(chk)가 중복되지 않도록 방문기록 2차원 배열을 2개 만듬. - 공통 : 양방향 이동이 가능하기 떄문에 a vertex 위치에 b를 append 하는 배열과 b, a 반대도 똑같이 배열에 넣는다. - BFS : 큐에 a와 b가 append괸 그래프 배열을 순서대로 삽입하고 방문한다. 방문기록도 Fals..
[BOJ] 18325. 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 해결 방법 """ 1. 아이디어 - a와 b로 이루어진 1차원 배열 m개, 방문 기록을 판단할 수 있는 1차원 배열 n+1개, 거리 값을 삽입시킨 1차원 배열 n+1개 - 시작지점 x부터 시작해서 BFS로 돌면서 이동거리 +1 2. 시간복잡도 - O(V + E) - V : 300000 - E : 1000000 3. 자료..
[BOJ] 2667. 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 2차원 배열 : int[][] - 방문 기록 : bool[][] - BFS를 돌면서 지도 각 단지의 연결된 아파트의 수를 구함. - 구한 아파트 수를 오름차순으로 출력. : sort() 2. 시간복잡도 - O(V + E) - V : 25 X 25 = 25^2 - E : 4 X 25 X 25 = 4 X 25^2 3. 자료구조 - BFS(Queue) - 2차원 배..
[BOJ] 1926. 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 1. 해결 방법 1. 아이디어 - 2중 for => 값 1 & 방문 x => BFS - BFS 돌면서 그림 개수 + 1, 최댓값을 갱신 2. 시간복잡도 (한번에 2억개를 실행) - BFS : O(V + E) - V : m(최대 500) X n(최대 500) = 250000 - E : 대략 V X 4(넉넉히) = 4 * 250000 - O : 5 * 250000 시간복잡도 문제 없음 3...

티스토리툴바