본문 바로가기

[PS] 문제풀이47

[ 백준 1260 ] DFS와 BFS (C++, DFS-BFS) [문제보기] 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [해결과정] DFS, BFS 사용 [소스코드] #include #include #include #include #include using namespace std; int n, m, s; int check[10005]; vector v[10005]; queue q; void dfs(int node){ cout s; for(int i=0; i> a >> b; v[a].push_back(b); v[b].push_ba.. 2021. 10. 22.
[ 백준 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.
[ 백준 1929 ] 소수 구하기 (C++, 에라토스테네스의 체) [문제보기] [해결과정] 에라토스테네스의 체 사용 -> 각 해당하는 수가 소수가 아닐 경우 그에 대한 배수는 모두 소수 처리하는 것 [소스코드] #include #include using namespace std; int n, m; int prime[1000005]={0,1,0,}; void isPrime(){ for(int i=2; i n >> m; isPrime(); for(int i=n; i 2021. 10. 22.
617. Merge Two Binary Trees ( LeetCode / JAVA / 안산학생 ) 617. Merge Two Binary Trees Merge Two Binary Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 - 모든 합계는 root1에 저장한다. - root1, root2 전위 순회 하며 root1에 값을 저장한다. 코드 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right.. 2021. 9. 12.
763. Partition Labels ( LeetCode / JAVA / 안산학생 ) 763. Partition Labels Partition Labels - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 - 새로운 배열을 만든다. - 입력 크기만큼 순회하며 [해당 알파벳]에 현재 순회 값을 저장한다. - 다시, 입력 크기만큼 순회하며 [순회 값 or 추 후 비교되어 큰 값]과 [해당 알파벳의 가장 뒷자리] 값을 비교하여 가장 큰 값을 저장한다. [순회 값]과 [알파벳의 가장 뒷자리] 수가 같아진다면 ans 배열에 등록한다. 코드 cla.. 2021. 9. 12.
[ 백준 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.
[ 백준 11659 ] 구간 합 구하기 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 사용 [소스코드] typedef long long ll; #include #include #include #include using namespace std; ll node[400000]; ll tree[400000]; // init(배열, 위치, 시작, 끝) ll init(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR){ if(dataIdxL == dataIdxR) return tree[treeIdx] = arr[dataIdxL-1]; ll mid = (dataIdxL + dataIdxR) / 2; return tree[treeIdx] = init(arr, 2*treeIdx, dataIdxL, mid) + init(arr,.. 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.
[ SWEA 2477 ] [모의 SW 역량테스트] 차량 정비소 ( C++ ) [문제보기] [해결과정] 1. input -> n, m, k, a, b -> nt[i] ( 접수 창고 걸리는 시간 ) , mt[i] ( 정비 창고 걸리는 시간 ) -> man[i].time ( 정비소 도착 시간 ) 2. func() 초기화 -> n1[i], m1[i] ( 접수 창고, 정비 창고 빈 곳으로 만들기 ) -> t = 0으로 시간 초기화 3. func() 내 while문 (1) 도착한 사람 큐에 넣기 (2) 접수 창고에 시간 다 된 사람 내보내기 (3) 접수 창고 비였으면 도착한 사람 넣기 (4) 정비 창고에 시간 다 된 사람 내보내기 (5) 정비 창고 비였으면 도착한 사람 넣기 (6) 만약 내보낸 사람 == 총 인원수 라면 끝내기 -> 아니라면 t++; [소스코드] [해결 과정 중 실수한 부분.. 2020. 4. 20.
[ 프로그래머스 42746 ] 가장 큰 수 (C++) [문제보기] [해결과정] 1. string 벡터 v 생성 2. v에 numbers를 string으로 변환하여 삽입 -> v.push_back(to_string(numbers[i])); 3. sort (정렬) - bool compare(string a, string b) 함수 사용 -> ( a + b > b + a ) return true; else false; a = 120 , b = 21 이라면 a+b = 12021 b+a = 21120 이렇게 문자열을 붙여서 int형으로 비교 하는 것이다. 4. 예외처리 -> v의 첫 원소에 "0"이 들어있다면, 최대 수가 0이라는 것이다. 그래서 return "0"; 5. 반복문을 돌며 answer에 v원소들 붙이기 [소스코드] [해결 과정 중 실수한 부분 / 잡담.. 2020. 4. 4.
[ 프로그래머스 42626 ] 더 맵게 (C++) [문제보기] [해결과정] 1. 오름차순 우선순위 큐 선언 (priority_queue) 2. vector 입력 값들을 모두 pq에 넣기 3. 만약 pq.top() 이 k 보다 같거나 크면 return; *** 왜냐하면 오름차순 우선순위 큐니까 가장 처음 값이 가장 작은 값이다. *** 가장 작은 값이 k 보다 같거나 크게 만들기 위한 문제다. 4. 무한 반복문 실행 - 예외처리1 : 만약 처음 값이 K 보다 같거나 크면 return answer; - 예외처리2 : 만약 큐 사이즈가 1이고, K 보다 작으면 return -1; (불가능한 경우) -> int a, b 변수 선언 -> a에 가장 첫 값 저장하고 큐 pop, b도 마찬가지.. *** 이렇게 하는 이유는 a에 가장 작은 값, b에 두번째로 작은 .. 2020. 4. 4.
[ 프로그래머스 42587 ] 프린터 (C++) [문제보기] [해결과정] 1. 큐(인자 2개), 우선순위 큐 생성 2. 벡터에 있는 것들을 큐에 삽입 -> 우선순위 큐에는 우선 순위 그대로.. -> 큐에는 우선 순위와 초기 위치 3. 무한 반복문을 돌며 큐의 중요도와 우선순위 큐의 맨 앞의 중요도를 비교 -> 만약 중요도가 같다면 pq.pop() 하고 answer++ -> 만약 순서가 location과 같다면 break; -> 중요도가 다르다면 현재 a,b를 q에 다시 삽입 [소스코드] 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 /* Programmers 42587 - 프린터 Created by haejun on .. 2020. 3. 31.

티스토리툴바