목록dfs (5)
데이터 엔지니어
문제링크: https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 문제 설명 - N: 정점의 개수 - 친구 관계 (u, v) N-1개 주어짐 위와 같은 입력이 주어졌을 때, 모든 노드와 관계를 맺고있는 최소의 노드 개수를 구하는 문제입니다. 여기서는 얼리어답터라고 칭합니다. 얼리어답터 = 관계를 맺는 주체 위와 같은 그림이 주어지면 2, 3, 4가 얼리어답터이고 나머지는 얼리어답터가 아닙니다. 최소의 개수는 3입니다. 1, 5, 6, 7, 8..
문제링크: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 설명 - L: 암호 자릿 수 - C: 알파벳 개수 - C개 알파벳으로 L 자릿 수의 암호를 만들 수 있는 모든 경우의 수를 사전순으로 출력 - 조건 1: 최소 1개의 모음 (a, e, i, o, u) - 조건 2: 최소 2개의 자음 - 조건 3: 오름차순 - 중복 x 모두 소문자 풀이 python 내장 라이브러리인 combination을 사용하여 해결하였습니다. 처음에는 permutat..
문제링크: https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제 설명 - 가로 세로가 n인 크기의 체스판에 n개의 queen을 놓을 수 있는 경우의 수 - queen은 가로 세로 대각선 이동이 가능 - n = 4 인경우 아래 이미지 처럼 2가지 경우의 수가 나옵니다. 풀이 - DFS / 백트래깅 (백트래킹은 지난 https://data-engineer.tistory.com/19에서 설명한 것 처..
문제링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 삼성 기출로 나왔던 문제입니다. 문제 설명 - N, M: 맵의 높이, 넓이 - 테트로미노: 정사각형 4개를 이어붙인 모양 - 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대 - 테트로미노들은 회전 대칭 가능 풀이 이 문제 같은 경우는 도형이 5개에다가 회전을 해도 총 경우의 수가 15가지 ex) ㅜ ㅏ ㅗ ㅓ (4가지) 가 나옵다. 각 지점마다 해당..
문제링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net dfs/bfs 기본문제를 풀어서 가장 유명한 문제인 단지 번호 붙이기 문제를 풀었습니다. 문제 설명 - 맵의 길이(N)이 주어짐 N * N - 1은 집이 있는 곳으로 단지를 구분해주어 개수를 오름차순으로 출력해주는 문제 풀이 방법 DFS / BFS 기본 문제 - 저는 queue를 사용하여 bfs로 풀이하였습니다. - 상하좌우 4가지 방향을 방문 하며 순회하면 된다. - visited로 ..