본문 바로가기

백준24

[ 백준 9095 ] 1, 2, 3 더하기 (C++) [문제보기] [해결과정] 재귀 사용 [소스코드] #include #include using namespace std; int t; int n; int arr[3] = {1,2,3}; int result; void func(int val, int sum){ // 기저조건 if(val == sum){ result++; return; }else if(val t; while(t--){ cin >> n; // 완전탐색 result = 0; func(n,0); cout 2021. 10. 22.
[ 백준 10868 ] 최솟값 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 활용 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTree[treeIdx] = arr[dataIdxL - 1]; ll mid = (dataIdxL + dataIdxR) / 2; return minTree.. 2021. 4. 17.
[ 백준 2357 ] 최솟값과 최댓값 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 활용 1. minTree, maxTree 구별 2. 각각 init함수와 query함수 작성 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll maxTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) // init_최소 트리 ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTre.. 2021. 4. 17.
[ 백준 15686 ] 치킨 배달 (C++) [문제보기] [해결과정] 1. 좌표 구조체를 생성한다. 2. 집 좌표 배열, 치킨 집 좌표 배열을 생성 - ★집은 2N개이다. (가장 많이 틀리는 부분) 3. 조합 (dfs) 수행 - M개의 치킨 집 고르기 4. 기저조건 상태라면, 집들을 돌며 치킨 집과의 거리를 구하고 가장 작은 거리를 sum에 더한다. 5. sum 값과 ans를 비교하여 ans 갱신 [소스코드] 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 .. 2020. 6. 3.
[ 백준 14502 ] 연구소 (C++) [문제보기] [해결과정] 1. 큐(bv) 생성 후 바이러스 좌표를 넣기. 2. 큐(q) 생성 3. dfs로 벽 3개 세우기 (조합 사용) - 세운 벽은 큐(q)에 넣기 4. 기저조건에 맞는 상태면 바이러스 활성화 해서 모두 퍼뜨리기 5. 가장 많은 빈공간이라면 답 갱신 6. 동작 후 맵은 원복, 방문 체크는 초기화 [소스코드] 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 7.. 2020. 6. 3.
[ 백준 17144 ] 미세먼지 안녕! (C++) [문제보기] [해결과정] 1. 공기청정기 위치를 저장할 구조체 생성 2. 기존 맵 1개, 기존 맵에서 먼지가 퍼지는 것을 저장할 맵 1개 생성 3. input 4. 기존 맵(map)을 돌며 먼지가 있으면 퍼지는 것을 저장할 맵(arr)에 계산 하여 저장 5. 주변에 퍼질 수 있는 공간에 퍼뜨리고, 그 수를 별도 저장. 6. 다 퍼뜨리고 해당 공간 계산 7. map에 arr맵을 복사하고, arr맵 초기화. 8. 위쪽 공기청정기, 아래쪽 공기청정기 순차적으로 수행 (반시계 경우, 시계방향으로 가며 칸을 끌어당기기) (시계 경우, 반시계방향으로 가며 칸을 끌어당기기) [소스코드] 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 2.. 2020. 6. 3.
[ 백준 10026 ] 적록색약 (C++) [문제보기] [해결과정] 1. input -> n, arr 입력받기 2. 정상인 사람이 볼 때, -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(0) 플래그 0으로 진입 3. bfs(0) -> bfs수행 하는데, flag가 0인 부분으로 진입 4. 적록색약인 사람이 볼 때, -> 먼저 check 배열 초기화, gNum = 0으로 변경 -> 맵을 순회하며 R을 G로 바꾸거나 혹은 G를 R로 다 바꿔버림. 5. 적록색약인 사람이 볼 때 기능 실행 -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(1) 플래그 .. 2020. 3. 18.
[ 백준 17142 ] 연구소3 (C++) [문제보기] [해결과정] 1. input -> n, m, arr 맵 --> 빈칸(0)의 갯수 카운트 하기 : if(arr 맵 == 0) k++ 2. DFS 완전탐색 -> 맵을 순회하며, 비활성바이러스를 발견하면, -1로 변경후 다음 DFS 수행 3. DFS 수행 중 Count 개수가 m과 같다면, 기능 실행 -> check 함수 -1로 초기화 -> DFS를 통해 활성바이러스로 바꾼 좌표를 큐에 삽입 (맵==-1) -> BFS() 수행 4. inf (0을 1로 바꾼 개수) , times (걸린 시간) 변수 선언 5. while(!q.empty()) 수행 -> 4방향 탐색하며, check == -1 && arr!=1 인 곳 방문 -> 만약 arr=0 이면 방문할 때 시간으로 times 갱신, inf++ 수행.. 2020. 3. 18.
[ 백준 16236 ] 아기 상어 (C++) [문제보기] [해결과정] 1. input ( n , arr에 맵 입력받기 ) -> 주의할점! 9는 상어의 초기 위치이다. 상어 위치를 다른 변수에 담고 맵에 9가 아닌 0으로 넣는다. 2. solution 수행 (1) 현재 상어 위치를 큐에 담는다 (2) BFS 수행 -> BFS를 돌며 현재 상어크기보다 같거나 작으면 진입 -> 만약 현재 상어크기보다 작으면 잡을 수 있는 물고기 ableFish++; -> 그리고 map값에 *=-1 하며 음수로 만들기 (음수인 곳은 잡을 수 있는 물고기란 뜻) -> minFish에 가장 작은 이동거리 저장시키기 (3) BFS가 끝나면, 맵 처음부터 끝까지 순회 -> 순회하며 음수인 곳을 가장 처음 만나는 곳이 잡아야 하는 물고기. -> 물고기를 잡고, 상어가 잡은 물고기.. 2020. 3. 11.
[ 백준 1076 ] 저항 (C++) [문제보기] [해결과정] 1. input : 3가지 색깔 (string) 2. 배열을 만들고, 색깔을 인자로 받고 값을 리턴하는 함수를 만들어, 각각의 색에 return 값을 만들어 준다. 3. 1번째와 2번째 배열 값들은 그대로 출력해주고, 3번째 배열 값 만큼 0을 반복하여 출력한다. -> 예외1 : 1번째 배열 값이 0인 경우, 2번째 배열 값만 출력 -> 예외2 : 1번째 배열 값과 2번째 배열 값이 0인 경우 0을 출력 [소스코드] 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 46 47 48 49 50 51 52 53.. 2020. 2. 29.
[ 백준 14503 ] 로봇 청소기 (C++) [문제보기] [해결과정] 1. input : n, m + 로봇 좌표 + 맵 2. 로봇 좌표와 방향을 담는 구조체와 큐 생성 후 큐에 좌표 넣기 3. 반복문 -> 큐에서 꺼낸 좌표가 청소되어있지 않다면 청소. -> 해당 좌표부터 왼쪽을 확인하며, 청소되어있지 않다면 진입. -> 만약 진입했다면 반복문 종류 후 continue; -> 만약 4방향 모두 청소되어있지 않다면 뒤로 이동... -> 만약 뒤로 이동할 수 없다면 전체 반복문 종료 [소스코드] 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 46 47 48 49 50 51 52.. 2020. 2. 28.
[ 백준 2851 ] 슈퍼 마리오 (C++) [문제보기] [해결과정] 1. input : arr(int형) 배열에 10개 버섯 담기 2. sum+=arr[i] 를 진행 -> 만약 절대값 sum+arr[i] -100 arr[i]; for (int i = 0; i 2020. 2. 27.
[ 백준 17471 ] 게리맨더링 (C++) [문제보기] [해결과정] 1. input : n, arr (int형) 배열에 각각의 인원수 담기 -> 2차원 vector에 각각의 점에 간선 긋기 2. dfs(int count, int r(레드갯수), int b(블루갯수)) -> count != n+1 이라면, color에 색칠 후에 dfs(count+1, 색칠한곳+1, 색칠안한곳) 전송 -> count == n+1 이라면 아래 3번 수행 3. function -> red, blue 각각의 진영 갯수 0으로 초기화 -> redSum, blueSum 각각의 총합 0으로 초기화 -> 방문 체크 배열(check) 초기화 -> rf, bf 플래그 초기화 -> 1~N까지 점을 돌며, 레드 진영 한번, 블루 진영 한번.. 각각 한번씩 정점을 큐에 넣고 그 색에 대.. 2020. 2. 27.
[ 백준 1712 ] 손익분기점 (C++) [문제보기] [해결과정] 1. input : long long int 타입으로 a, b, c 입력 2. a + bx > cx 를 찾기 -> 예외 처리 b>=c 인 경우... [소스코드] 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 /* BOJ 1712 - 손익분기점 Created by haejun on 2020/02/27 */ #include #include #include #include #include #include using namespace std; #define ll long long int ll a, b, c; int main(){ ios_base::sync_with_stdio(0); cin... 2020. 2. 27.
[ 백준 1405 ] 미친 로봇 (C++) [문제보기] [해결과정] 1. input : n, double 형 d[4] ( 동, 서, 남, 북 ) -> d[i]/=100으로 해서 소수점으로 변환 2. 동, 서, 남, 북으로 이동하는 것을 맵에서 check 하기 위해서 map배열을 만들어준다. -> 맵의 가장 중앙 지점을 방문 처리 한다. 3. 맵의 가장 중앙 지점 부터 dfs 실행 -> dfs(y,x, cnt, p) cnt는 dfs count이고, p는 확률(소수)를 담을 변수 -> 만약, 단순한 경로(겹치지 않는 경로) 일 경우 ret += p -> 현재까지의 확률을 정답란에 저장 -> 만약, 단순한 경로가 아닌 경우(이미 방문한 지점을 방문) 패스 4. output : 소수점 11자리 까지 지정하여 출력 -> cout.precision(11);.. 2020. 2. 26.

티스토리툴바