본문 바로가기
반응형

전체 글1306

[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.
[BOJ] 백준 5582 공통 부분 문자열 출처: https://www.acmicpc.net/problem/5582 Input ABRACADABRA ECADADABRBCRDARA Output 5 DP[i][j] = A 문자열의 i번째 문자와 B문자열의 j번째 문자가 공통 부분 문자열의 마지막 문자로 하는 공통부분문자열의 최대 길이 if (A[i] == B[j]) D[i][j] = D[i - 1][j - 1] + 1; #include const int LM = 4002; int an, bn, D[LM][LM], ans; char A[LM], B[LM]; int main() { scanf("%s %s", A + 1, B + 1); for (int i = 1; A[i]; ++i) { for (int j = 1; B[j]; ++j) { if (A[i] .. 2021. 2. 25.
[BOJ] 백준 3653 영화 수집 출처: https://www.acmicpc.net/problem/3653 Input 2 3 3 3 1 1 5 3 4 4 5 Output 2 1 0 3 0 4 처음 DVD가 놓인 위치를 M+1 ~ N까지 『1』로 표시합니다. 그리고 각 DVD의 위치를 pos[] 배열에 저장합니다. Q) 4번째(= pos[4]) 놓인 DVD 위에 쌓여있는 DVD의 개수는? ▶ 1 ~ (7-1)까지 구간의 합 = 3개입니다. Q) 선택된 4번째 DVD를 어디로 옮기면 될까? ▶ 처음 M부터 해서 시작해서 1번째까지 입니다. (next = M) (그렇기 때문에 N 크기 앞에 M만큼 배열 크기 할당) Q) 여기서 4번째(pos[4] = 3) DVD 위에 놓인 DVD 개수는? 구간 [1, 3-1]까지의 구간합 = 0 + 0 = 0.. 2021. 2. 25.
반응형

티스토리툴바