BBLOG

[URL] https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이 과정] 1. 조건에 맞게 기본 DFS 시전 2. sum += PAY[pos]; 3. pos: 1~ N까지 다 검사 후 sum 중 최대값 출력 [소스 코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// 4. 퇴사// https://www.acmicpc.net/problem/14501 #include #include using namespace std; int N;int Time[16]..

[URL] https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com [풀이 과정] * 재귀DFS 2진탐색 (깊이 N까지) [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 ..

[URL] https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net [풀이 과정] *그래프 구현(벡터), 깊이우선탐색(DFS) 1. 배열로 깊이 우선 탐색 (시간 초과) 2. 그래프 깊이 우선 탐색 3. 연결관계 4개 찾으면 flag = 1로 바꿔주고 flag 값 검색하여 1이면 return; [소스 코드] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include ..

[URL] https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com [풀이 과정] * DFS 1. 가능한 최대 코어 개수를 구한다. DFS1(); 2. 가능한 최대 코어 개수일때 연결 가능한 전선 개수 중 최소값 구한다. DFS2(); [소스 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

[URL] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net [풀이 과정] * DFS (기존 단지번호 붙이기 문제와 유사) 1. 그룹화가 우선 --> 그룹이 생기지 않으면 종료 2. ..

[URL] https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net [풀이 과정] * 재귀, DFS, BFS 1. 재귀 DFS로 3개의 벽 선정 2. 3개 벽 세워 두고 바이러스(map[][] =..

[URL] https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com [풀이 과정] ​ 1. DFS & 백트래킹 문제 2. 유망성 검토를 통하여 완전 탐색 중 백트래킹을 통하여 check하는 설정 3. 퀸 놓는 방법 map[][] == 0 인 경우 놓을 수 있다. 4. 퀸 하나를 놓을 경우 -> map[][]에 안되는 부분(가로, 세로, 대각선1, 대각선 ..

[URL] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net [풀이 과정] *단순 재귀DFS 1. map[][] == 1인 곳 vector v에 push 2. v만큼 for문 돌며 재귀 dfs() 3. 첫번째 단지..

[URL] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net [풀이 과정] * 재귀 DFS 1. 재귀 DFS를 활용하여 가능한 연산자 조합을 구한다. ex) [+] [-] [*] [%] [2] [0] [1] [0] 일때 (1) + + * (2) + * + (3) * + + 3가지 조합 가능 2. 각각의 조합에 따라 연산 실행 3. 후보자 배열에 넣..

[URL] https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [풀이 과정] * DFS 재귀 두번 해야한다. 1. 1~N까지의 수를 두개(A팀, B팀)로 나눠 모든 경우의 수 계산 2. 각각의 경우의 수에서 A팀 중 두개씩 묶어서 능력치 계산 ex) N= 6, A팀 : [1, 2, 3] B팀 : [4, 5, 6] 일 때 A팀 능력치: map[1][2] + map[2][1] + map[2][3] + map[3][2] + map[1][3] + map[3][1] B팀 능력치..