본문 바로가기
반응형

분류 전체보기1308

[BOJ] 백준 1158 요세푸스 문제 출처: https://www.acmicpc.net/problem/1158 Input 7 3 Output 배열에서 K번째 원소를 찾은 후, 제거된 순서대로 Queue에 넣어줍니다. K 번째 원소를 찾을 때 원형 큐를 찾거나, 원소를 재배치하여 처리할 수 있습니다. (※ 제출 코드에는 원소를 재배열하여 탐색) import java.util.Scanner; class Queue { int front, rear; int[] queue; public Queue(int size) { front = 0; rear = 0; queue = new int[size]; } public void push(int value) { queue[rear++] = value; } public int pop(int idx) { int .. 2021. 2. 25.
[BOJ] 백준 2458 키 순서 출처: https://www.acmicpc.net/problem/2458 Approach 그래프 관계를 표현 → a가 b보다 작다면 a에서 b로 화살표 표현 Q. 자신의 키 순서를 알 수 있는 방법은 무엇이 있을까? A. 자신보다 키가 큰 사람의 수 x와 작은 사람의 y → x + y = N-1 인 경우입니다. 즉, 대소 판별이 가능한 수가 N-1명인 경우 자신이 몇번째인지 알 수 있습니다. * cnt[i] : i번째 학생과 대/소 판별이 가능한 학생 수로 정의 그래프에서 정점별로 방문한 가능한 곳을 탐색하는데 (자기자신 제외, 재방문 X) 대소 비교가 되었던 학생은 cnt[A]++, cnt[B]++ 처리합니다. 결과적으로 cnt[i] == N-1인 학생들의 수가 대/소 판별이 가능한 학생입니다. 시뮬레.. 2021. 2. 25.
[BOJ] 백준 1406 에디터 출처: https://www.acmicpc.net/problem/1406 Input abcd 3 P x L P y Output abcdyx 이중연결 리스트를 구현해서 cur 포인터를 통해 커서를 구현할 수 있습니다. - L 인 경우 이동가능하다면 cur 를 왼쪽으로 이동시킨다 - D 인 경우 이동가능하다면 cur 를 오른쪽으로 이동시킨다 - B 인 경우 지울 수 있다면 cur 의 데이터를 지우고, cur 를 왼쪽 노드로 이동시킨다 - P $ 인 경우 cur 의 next 에 새로운 노드를 추가하고, cur 를 오른쪽 노드로 이동시킨다 #define _CRT_SECURE_NO_WARNINGS #include #define LM 100050 struct Node { char data; Node *prev, *.. 2021. 2. 25.
[BOJ] 백준 3033 가장 긴 문자열 출처: https://www.acmicpc.net/problem/3033 Input 11 sabcabcfabc Output 3 ▶ 문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것 찾기 (부분 문자열은 일부가 겹쳐서 등장할 수도 있다.) (두 번이상이므로 3번 이상 확인할 필요 없이 두 번 등장하였는지만 확인) ex) "aaa" → 두 번 이상 등장하는 가장 긴 문자열 "aa" 두 번 이상 등장하는 문자열이 있을 때, → 첫 번째 문자열은 str[0] ~ str[L-2] 사이에서 시작 → 두 번째 문자열은 str[1] ~ str[L-1] 사이에서 시작 if) 완전 탐색하는 경우 O(L2)으로 TLE 발생 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되.. 2021. 2. 25.
[BOJ] 백준 7453 합이 0인 네 정수 출처: https://www.acmicpc.net/problem/7453 Input 6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45 Output 5 ▶ A + B + C + D = 0 -45 + -27 + 42 + 30 = 0 26 + 30 + -10 + -46 = 0 -32 + 22 + 56 + -46 = 0 -32 + 30 + -75 + 77 = 0 -32 + -54 + 56 + 30 = 0 [방법 1] Brute Force ▶ 4중 반복문을 구현하여 완전탐색으로 구할 수 있지만 TLE 발생 [방법 2] Radix Sort ▶ A + B + C + D = 0 → (A + B) = -(C + D).. 2021. 2. 25.
[BOJ] 백준 17619 개구리 점프 출처: https://www.acmicpc.net/problem/17619 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 통나무 A에서 통나무 B로 갈 수 있다는 것은 두 통나무의 X좌표 구간이 교집합(겹치는 구간)을 가집니다. 즉, Y좌표는 정답을 구하는데 아무런 영향을 미치지 않는다. 만약, A와 B 두 통나무 사이에 다른 통나무들이 존재한다면 그 통나무들을 거쳐서 가면 된다. .. 2021. 2. 25.
[BOJ] 백준 17615 볼 모으기 출처: https://www.acmicpc.net/problem/17615 Input 9 RBBBRBRRR Output 2 ① 각 색깔의 개수를 센다. (빨간색 볼, 파란색 볼의 개수) → 더 적은 개수의 색깔을 지닌 공을 옮기는 것이 효율적입니다. ② 왼쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다. → 기존의 답보다 작으면 갱신 (나머지 볼을 왼쪽으로 옮기는 경우) ③ 오른쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다. → 기존의 답보다 작으면 갱신 (나머지 볼을 오른쪽으로 옮기는 경우) R B B B R B R R R ① 빨간색볼이 5 개, 파란색볼이 4 개로 정답 후보는 4 이다. ② 왼쪽부터 연속한 볼은 빨간색 1 개이다. → 빨간색볼이 총 5 개이.. 2021. 2. 25.
[BOJ] 백준 2450 모양 정돈 출처: https://www.acmicpc.net/problem/2450 Input 8 1 3 3 2 1 1 3 2 Output 2 정돈된 최종 모양은 총 6가지 입니다. order[] = [1 2 3] / [1 3 2] / [2 1 3] / [2 3 1] / [3 1 2] / [3 2 1] 위의 경우 [동그라미, 네모, 세모]로 [3 2 1] 구성으로 모여있다고 볼 수 있습니다. 각각의 경우를 구성하기 위해 바꾸기 횟수를 구해보면 됩니다. ① 6가지 경우 중 order[]를 하나 정해놓고 ② 해당 위치에 있는 다른 모양의 개수를 세어서 교환해야 하는 횟수를 계산 시뮬레이션 배치하고자하는 순서 order[] = [3 2 1]일 때, arr[] = [1 3 3 2 1 1 3 2] → cnt[] = [3 2.. 2021. 2. 25.
[BOJ] 백준 10709 기상캐스터 출처: https://www.acmicpc.net/problem/10709 Input 3 4 c..c ..c. .... Output 0 1 2 0 -1 -1 0 1 -1 -1 -1 -1 [구름의 움직임] ① 처음 구름이 있는 위치를 『0』 구름이 없는 위치를 『-1』 ② 한 행씩 오른쪽으로 탐색하면서 구름이 처음 있었던 위치이면 continue 구름이 없는 위치라면 왼쪽 지점에서 구름이 보이는 시점 + 1 처리 #define _CRT_SECURE_NO_WARNINGS #include char map[100][100]; int W, H, board[100][100]; int main() { // freopen("input.txt", "r", stdin); int i, j; scanf("%d %d", &W,.. 2021. 2. 25.
[BOJ] 백준 2641 다각형 그리기 출처: https://www.acmicpc.net/problem/2641 Input 10 1 4 1 1 4 3 3 3 2 2 3 3 2 2 1 4 1 1 4 3 3 1 4 4 3 3 3 2 1 1 2 4 4 1 1 1 2 3 3 2 3 Output 2 3 2 2 1 4 1 1 4 3 3 4 4 1 1 1 2 3 3 2 3 문제에서 모양수열은 한 개의 다각형을 그리기에 출발점만 다를 뿐 그려지는 모양은 같습니다. - 점 A에서 출발하는 다각형 (2): 1 4 1 1 4 3 3 3 2 2 - 점 B에서 출발하는 다각형 (3): 3 2 2 1 4 1 1 4 3 3 그렇기에 이차원 배열에 따로 다각형 모양을 그려서 비교하지 않고, 주어지는 모양수열 원소를 하나의 출발점으로 생각하며 똑같은 경로를 그리는지 확인합.. 2021. 2. 25.
반응형

티스토리툴바