본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 11758 CCW 출처: https://www.acmicpc.net/problem/11758 Input 1 1 5 5 7 3 Output -1 3개의 좌표를 토대로 기하와 벡터 공식을 이용하면 쉽게 알 수 있습니다. - S 0 반시계 방향 - S = 0 일직선(평행) import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; Point[] points = new Po.. 2021. 2. 28.
[BOJ] 백준 4354 문자열 제곱 출처: https://www.acmicpc.net/problem/4354 Input abcd aaaa ababab . Output 1 4 3 ▶ (abcd)1 / (a)4 / (ab)3 주어진 문자열에서 최대한 짧은 부분 문자열을 거듭 이용해서 전체 문자열을 만들어야 합니다. ex) "abababab"는 "ab"를 4번 반복하면 만들 수 있습니다. KMP알고리즘에서 실패 함수 테이블의 맨 마지막 값을 구합니다. 실패함수가 반복되는 패턴(Pattern)을 찾아내는 것이기 때문입니다. ex) S = "ababab"의 실패 함수 마지막 값은 pi[S.length() - 1] = 4 입니다. 여기서, S.length() - pi[S.length() - 1] = 6 - 4 = 2 입니다. ← 반복되는 문자열 크기.. 2021. 2. 28.
[BOJ] 백준 3055 탈출 출처: https://www.acmicpc.net/problem/3055 Input 3 6 D...*. .X.X.. ....S. Output 6 물이 확장되는 BFS와 고슴도치가 이동하는 BFS 각각 구현 고슴도치가 물이 찰 예정인 곳을 이동할 수 없으므로 물에 대한 BFS를 먼저 수행한 후, 고슴도치 이동에 대한 BFS 수행. #include #include #define endl "\n" #define MAX 50 using namespace std; int R, C; char map[MAX][MAX]; bool visited[MAX][MAX]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; pair startPos, endPos; queue wa.. 2021. 2. 27.
[BOJ] 백준 2503 숫자 야구 출처: https://www.acmicpc.net/problem/2503 Input 4 123 1 1 356 1 0 327 2 0 489 0 1 Output 2 ▶ 완전탐색 접근 3자리의 숫자는 1~9까지의 서로 다른 숫자로 구성되어야 합니다. 따라서 123~999까지 숫자 0을 포함하거나 동일한 숫자가 나오는 경우를 제외합니다. ex) 133, 999, 150 등 그 외의 경우) B가 제시한 숫자들과 자리 및 동일한 숫자이지 확인하여 A가 답변한 strike 개수, ball 개수 비교 (문답한 N개를 모두 만족해야 합니다.) #include #include #include #include using namespace std; typedef struct{ string number; int strikeCn.. 2021. 2. 27.
[BOJ] 백준 2533 사회망 서비스(SNS) (Greedy) 출처: https://www.acmicpc.net/problem/2533 Input 8 1 2 1 3 1 4 2 5 2 6 4 7 4 8 Output 3 Greedy 방식 트리 구조이므로 "단말 노드 개수 ≥ 단말 노드 부모 개수" 이는 단말 노드를 얼리어댑터로 설정하는 것이 전체 얼리어댑터의 개수를 최소화하는데 도움이 되지 않습니다. 단말 노드보다 부모 노드를 얼리 어댑터로 설정하는 것이 전체 얼리어댑터 개수를 최소화하는 것입니다. 단말 노드를 얼리어댑터로 하지 않았다고 생각하면 단말 노드의 부모는 반드시 얼리어댑터이어야 합니다. 그리고 아랫부분을 제외해서 또 다른 부분 문제로 생각할 수 있습니다. child가 모두 얼리어댑터라면 부모 노드는 얼리어댑터로 선택하지 않는다. child에 얼리어댑터가 아닌.. 2021. 2. 27.
[BOJ] 백준 2533 사회망 서비스(SNS) 출처: https://www.acmicpc.net/problem/2533 Input 8 1 2 1 3 1 4 2 5 2 6 4 7 4 8 Output 3 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com "사회망 서비스에 속한 사람들은 얼리 어댑터이거나 얼리 어댑터가 아니다." "얼리 어댑터가 아닌 사람들은 자신의 모든 친구들이 얼리 어댑터일 때만 이 아이디어를 받아들인다." → 두 사람이 친구 사이.. 2021. 2. 27.
[BOJ] 백준 1655 가운데를 말해요 출처: https://www.acmicpc.net/problem/1655 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 TLE 발생. 우선순위 큐 사용하여 해결 < 최대 힙(Max heap)과 최소 힙(Min heap) 구조 이용 1. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다. 2. 값을 넣어준 후 최대 힙과 최소 힙의 t.. 2021. 2. 27.
[BOJ] 백준 2696 중앙값 구하기 출처: https://www.acmicpc.net/problem/2696 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 우선순위 큐 이용 (C++ STL priority_queue는 내부적으로 Heap 구조로 이루어져 있음) - 우선순위큐를 2개 준비 (최대 힙과 최소 힙) - 새로운 원소가 들어올 때 다음의 과정 수행 ① 두 개의 큐에 쌓인 원소의 개수 비교 - 같으면 maxHeap에 push - 다르면 minHeap에 push 결과적으로 maxHeap의.. 2021. 2. 27.
[BOJ] 백준 17612 쇼핑몰 출처: https://www.acmicpc.net/problem/17612 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 먼저 대기하고 있는 고객이 계산대에서 물건을 계산하고 쇼핑몰을 빠져 나갑니다. → FIFO (First In First Out) - 계산대가 2개이상 동시에 비는 경우 낮은 번호 계산대에 먼저 배정 ex) 3번, 5번 계산대가 비게된다면 3번으로 안내 - 계산이 동시에 끝나는 경우에는 (출구에 가까운)높은 번호 계산대에 있는 고객이 먼저.. 2021. 2. 27.
[BOJ] 백준 2549 루빅의 사각형 출처: https://www.acmicpc.net/problem/2549 Input 1 2 15 4 7 8 3 6 9 10 5 12 13 14 11 16 Output 2 2 3 3 1 2 2 문제에서 정의한 한번의 움직임은 3가지 움직임을 의미합니다. 1칸 회전 = 2칸 회전 = 3칸 회전 = 한번의 움직임 따라서 매 단계 선택할 수 있는 경우의 수는 → (행 4 + 열 4) * 회전 3가지(1, 2, 3) = 24가지 ※ 회전의 경우 4cylce 주기를 갖고 있음 주어진 회전 횟수는 최대 7번 이므로 247이며, 16개 타일이 맞는 위치에 있는지 확인해야 하므로 → O(247 * 16) = O(73,383,542,784) 완전 탐색으로 이 모든 경우를 구현한다면 TLE 발생 따라서, 전체 경우를 살피는.. 2021. 2. 27.
반응형

티스토리툴바