본문 바로가기

전체 글

 (351)
[BOJ] 15651. N과 M (3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택 - 중복이 가능하기 때문에 방문기록을 할 필요가 없음 - 재귀함수에서 M개를 선택할 경우 print 2. 시간복잡도 - 중복 허용 N^N ( N
[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. 자료..
[RabbitMQ] RabbitMQ 설치하기. (Feat. Docker) 추 후에 래빗엠큐을 제대로 이해하기 위해서 글을 올릴 예정이지만, 간단하게 설명을 하면, RabbitMQ는 AMQP(Advanced Message Queuing Protocol)을 구현한 메시지 브로커이다. 브로커는 일반적인 의미와 같이 메시지를 중계하는 역할을 한다. 그러면 RabbitMQ는 무슨 중계 역할을 할까? 간략해서 말하면, 메시지를 쉽게 전송할 수 있는 메시지 큐 기능을 제공한다. 본인은 ELK Stack과 함께 로그 수집을 효율적으로 하기 위해서 RabbitMQ를 사용하려 한다. 1. 준비 사항 https://musclebear.tistory.com/139 [RabbitMQ] docker로 래빗 MQ 설치하기 개요 RabbitMQ란? RabbitMQ는 AMQP(Advanced Message..
[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차원 배..

티스토리툴바