본문 바로가기
반응형

분류 전체보기1311

[BOJ] 백준 21608 상어 초등학교 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21608 Approach BFS + 완전탐색을 구현하는 문제이다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com ① N * N 명의 친구들을 입력받은 순서대로 배치한다. ② 문제에서 주어진 우선순위에 따라 map[][]에 배치한다. → isBetter.. 2021. 5. 23.
[BOJ] 백준 10759 팰린드롬 경로 3 출처: https://www.acmicpc.net/problem/10759 Approach DP[][] = 문자열이 팰린드롬인 경우의 수 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com #include #define LL long long const int MAX_N = 500 + 2; const int MOD = 1000000007; inline LL add(LL A, LL B) { return .. 2021. 5. 22.
[SWEA] 4534 트리 흑백 색칠 출처: SWEA Approach 메모제이션을 이용해서 풀 수 있는 문제이다. DP[Color][Node] = Node에서 Color를 가질 때, 가질 수 있는 최대 색칠 방법 수 - DP[흰색][node] = DP[검은색][next] + DP[흰색][next] - DP[검은색][node] = DP[흰색][next] 변수 계산에서 int 범위를 벗어나기 때문에 long long 타입이 필요하고 MOD로 나머지 연산(%) 처리해야 한다. ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각.. 2021. 5. 22.
동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법(DP)은 다른 알고리즘과 함께 이용해서 문제를 풀어야 하는 경우가 있다. 특정 Case를 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용하여 속도를 높이다. 그러기 위해 각 문제의 답을 메모리에 저장해 둘 필요가 있다. → DP[ ][ ] ▶ 연속된 부분 합(연속합) - 1 (완전 탐색) ▶ 연속된 부분 합(연속합) - 2 (Prefix Sum) ▶ 연속된 부분 합(연속합.. 2021. 5. 22.
[SWEA] 9236 곰돌이 출처: SWEA Approach ① Input Data를 입력 받아 base[][]에 저장한다. 벌(bee)과 곰돌이(bear) 이동을 확인하기 위해 BFS를 여러번 해야 하는데 이를 위해 base[][]를 원본으로 활용 - 곰돌이 위치(M), 집 위치(D), 벌의 초기 위치(H)를 표시한다. ② 벌들을 확산시킨다. 확산되는 원리는 BFS 방식을 이용한다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 z.. 2021. 5. 22.
[SWEA] 4747 사막에서 만난 지니 출처: SWEA Approach 문제를 맞추려면 조건 中에서 3 ≤ N ≤ 2000 와 1 ≤ V ≤ 10000 조건을 만족해야 한다. 개수 상관없이 3명의 아이들에게 동일한 값어치를 분배할 때, 각자 받은 물건의 값어치는 배낭에 있었던 물건들의 {총 값어치 ÷ 3} 이다. ex) {1, 2, 3, 4, 5} → 1 + 2 + 3 + 4 + 5 → 15 ÷ 3 = 5 (=아이들이 받은 물건의 값어치) 즉, 평균(avg)에 해당하는 것을 알 수 있다. 다음 고려해야 할 부분은 어떻게 분배해야 할 것인지이다. Input Data에서 한 사람당 받은 물건의 총 값어치를 알 수 있기에 1번에게 물건 배정 → 2번에게 물건 배정까지 한다면 남은 한 사람 3번은 나머지 물건을 가지며 될 것이다. 문제에서 "항상 물.. 2021. 5. 22.
[SWEA] 7794 동환이의 알뜰살뜰 출처: SWEA Approach 문제에서도 명시되어 있지만 할인금액은 아래와 같이 계산할 수 있다. 1% → 0.99 2% → 0.98 3% → 0.97 ex) 100만원, 3% 할인 적용 → 100 × 0.97 = 97만원 36만원, 2% + 3% 할인 쿠폰 적용 → 36 × 0.98 × 0.97 = 34.2216만원 구조체 배열 coupon[]에 할인 정보 저장 ex) 상품가격 = 100, 쿠폰 가격 = 1, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {1, 0.97, 2} ex) 상품가격 = 100, 쿠폰 가격 = 2, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {2, 0.97, 1} ▶ 동일한 할인.. 2021. 5. 21.
[SWEA] 8569 개미 관찰 출처: SWEA Approach Parametric Search 를 적용하는 문제이다. [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐.. zoosso.tistory.com Lower Bound를 이용하는데 해당 개념에 대해 모른다면 아래 내용도 함께 참고 ▶ Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O.. 2021. 5. 20.
[SWEA] 8744 도로 제거 출처: SWEA Approach N개의 도시를 서로 한번씩 연결하면 (N × (N-1)) ÷ 2 의 간선이 생긴다. ex) N = 4 → (4 × 3) ÷ 2 = 6 "어떤 k개의 도로 폐쇄해도 서로 다른 두 도시간에 이동할 수 있음이 유지되도록 하고 싶다" 위 문제 조건을 이해한다면 어렵지 않게 구현할 수 있는 문제이다. 위 모습은 2(= M) 개의 간선을 제거한 상태이다. (각 도시에 남아있는 도로 개수는 {빨간 숫자}로 표시) "이동될 수 있음"을 보장하면서 도로를 추가로 제거한다면 도로 {② ↔ ④} 1(=k)개를 제거하거나 도로 {① ↔ ④}를 1(=k)개를 제거할 수 있다. 하지만 어떤 k개의 도로를 폐쇄해도 서로 다른 두 도시로 이동되어야 하기 때문에 제거되는 1개 도로가 {③ ↔ ④}가 된.. 2021. 5. 19.
[SWEA] 1248 공통조상 출처: SWEA Approach 노드 [8]의 부모노드는 [5]이며, [13]의 부모노드는 [11]이다. 위로 올라가면 공통 조상격인 [3]과 [1]이 있으며 가까운 공통 조상은 [3]이 된다. 가장 가까운 공통 조상노드를 기준으로 하였을 때, 서브트리의 크기는 아래와 같다. (기준 노드를 포함한 수치) ① 구조체로 트리(Tree) 구현 - 이진트리이므로 왼쪽/오른쪽 자식노드를 순차적으로 구성 - 공통 조상을 탐색하기 위해 부모노드 표시 ② 첫번째 대상 노드를 시작으로 부모 노드(들) 표시 ex) 정점 [8]에 대해서 [5] → [3] → [1] 노드들이 vistied[] 표시된다. ③ 두번째 대상 노드를 시작으로 조상 노드 추적 ex) [13]을 기준으로 조상 노드를 추적할 때, [11] → [6] →.. 2021. 5. 17.
반응형

티스토리툴바