본문 바로가기
반응형

dfs5

[LeetCode] 886. Possible Bipartition [JAVA(자바)] '기술면접 라이브코딩 - 승지니어'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 () N명의 사람을 두 그룹으로 나눈다. Dislikes[i] = [a,b] 일 때, a 와 b 는 서로 다른 그룹이어야 한다. Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4], group2 [2,3] Input: N = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false 2. 풀이 이분그래프 와 DFS 를 이용한 풀이 이분그래프를 통해 N명의 사람을 2개의 그룹으로 나눈다. DFS 를 통해 dislikes한 사람을 모두 다른 그룹(true/false)으로 보낸다. visi.. 2021. 11. 24.
[백준] 16234 - 인구 이동 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 16234번: 인구 이동 1. 문제 N*N크기의 땅이 있고, 각각의 땅에는 나라가 존재한다. 각 나라의 칸에는 인구 수가 적혀있고, 인접한 나라 사이에는 국경선이 존재한다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는.. 2021. 11. 22.
[백준] 14503 - 로봇 청소기 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 14503번: 로봇 청소기 1. 문제 로봇 청소기가 청소하는 영역 NxM이 주어지며, 각각의 칸은 벽(1) 또는 빈 칸(0)이다. 로봇 청소기는 다음과 같이 동작한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도.. 2021. 11. 22.
[백준] 14502 - 연구소 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 14502번: 연구소 1. 문제 N*M 크기의 연구소는 빈 칸(0)과 벽(1) 그리고 바이러스(2)로 이루어져있다. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 추가로 3개의 벽을 세워 바이러스가 가장 적게 퍼지게 한다. 안정 영역의 최댓값을 출력한다. -> 바이러스가 최소일 때를 구하는 문제 2. 풀이 브루트포스 와 DFS를 이용한 문제 풀이 바이러스의 최솟값을 구한다. 초기 빈 칸의 개수와 바이러스 위치를 저장 브루트포스를 통해 3개의 벽을 세울 수 있는 모든 경우를 고려한다. DFS를 통해 바이러스의 총 개수를 구한다. 안전 영역 = 총 빈칸 - 최소 바이러스 개수 - 벽의 개수(3) 3. 코드 N, M = map(int.. 2021. 11. 22.
[백준] 14501 - 퇴사 [Python(파이썬)] '삼성 SW 역량 테스트' 기출 문제 입니다. 😀 문제 👉 14501번: 퇴사 1. 문제 상담 일정표는 상담 기간과 상담 금액으로 이루어져 있다. N일 동안 적절한 상담 조합을 통해 구할 수 있는 최대 금액을 출력한다. 2. 풀이 DP(Dynamic Programming)을 이용한 문제 풀이 크기가 N인 DP 배열 생성 당일 상담이 퇴사 전에 가능할 경우 상담 선택한다. 당일 이전에 상담이 끝나는 날 중 보상이 가장 큰 날의 보상을 당일 보상에 더한다. DP배열에서 가장 보상이 큰 날을 return 3. 코드 def solution(): N = int(input()) L = [list(map(int, input().split())) for _ in range(N)] dp = [0]*N # N일 동안 선택.. 2021. 11. 22.
반응형

티스토리툴바