본문 바로가기

전체 글239

분할 정복 분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 대표적 예는 정렬 알고리즘 중에서 퀵, 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다. 분할정복법의 설계전략? 분할 : 문제 사례를 하나 이상의 작은 사례로 분할(Divide) 합니다. 정복 : 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 재귀를 사용합니다. 병합 : 필요하다면, 작은 사례에 대한 해답을 통한(Combine)하여 원래 사례의 해답을 구합니다. 분할정복법의 장단점? 장점 Top-down 재귀 방식으로 구현하기 때문에 코드가 직관적입니다. 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결 단점 재귀 함수 호출로 오버헤드가 발.. 2022. 6. 8.
투 포인터 (Two Pointer) 투포인터 정렬된 리스트를 두 개의 포인터를 가지고 순차적으로 접근하면서, 두 포인터 구간의 값이 타겟 값과 같을 때까지 포인터를 조작하는 기법을 말합니다. 투포인터 알고리즘에 대해서는 검색만 해도 어떻게 로직이 돌아가는 지 쉽게 이해할 수 있을 거 같아서 저는 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점이 무엇인 지에 대해서 글을 써볼까 했습니다. 사실 이점은 1차원 배열을 한 번의 루프로 문제의 원하는 결과를 얻을 수 있다는 점입니다. 코딩테스트 문제마다 다르겠지만, 저는 수들의 합2(2003) 문제를 가지고 비교를 해보았습니다. 결과는 사실 복잡도에서 큰 차이를 못느꼈습니다. 하지만, 새로운 알고리즘 유형이니 익힐 필요성은 있다고 생각했습니다. 그리고 투포인터 알고리즘은 구현 방식이 문제 별.. 2022. 6. 7.
이진탐색 == 이분탐색 (Binary Search) 이란? 이진탐색 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. (정렬된 배열, 리스트에 적합한) 배열의 중앙에 있는 값을 조사하여, 찾고자하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는 지를 알아내어 탐색의 범위를 반으로 줄입니다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있습니다. 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합합니다. 이진탐색의 시간 복잡도 한 번 확인할 때마다 확인하는 원소의 개수가 절반 씩 줄어든다는 점에서 시간 복잡도가 O(logN)입니다. 예시 1. 10억 명의 어떠한 이름이 저장되어있는 배열에서 이진 탐색을 이용해 특정한 이름을 찾는 경.. 2022. 6. 3.
[백준 *Java] - 4연산(14395) 4연산 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오. 사용할 수 있는 연산은 아래와 같다. s = s + s; (출력: +) s = s - s; (출력: -) s = s * s; (출력: *) s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능) 입력 첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109) 출력 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 .. 2022. 6. 3.
[백준 *Java] - 2048(Easy)(12100) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제는 사진이 많아서, 따로 블로그에 적지 않겠습니다. 👇 접근방식 문제를 보았을 때, 사방 탐색 문제라는 걸 알았습니다. dfs 또는 bfs 문제인데, 일단 최소가아니라 depth(5)가 정해져있으니, dfs 로 문제를 풀어야겠다고 생각했습니다. 일단 생각으론 NxN 칸을 매 번 이동 시켰을 시, 기억을 해주어야하며? 그리고 이동했던 방향까지 기억을 해야한다고 생각하.. 2022. 5. 16.
SW - 새샘이의7-3-5 게임 (Diff3) https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWZ2IErKCwUDFAUQ&categoryId=AWZ2IErKCwUDFAUQ&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=9&&&&&&&&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제] 숫자게임을 좋아하는 새샘이는 서로 다른 7개의 정수 중에서 3개의 정수를 골라 합을 구해서 수.. 2022. 5. 15.

티스토리툴바