자료구조, 알고리즘/알고리즘

[알고리즘] 그리디

| 그리디란? - 그리디 알고리즘은, 매 선택에서 지금 이 순간 가장 최선이라 생각되는 답을 선택해 결과를 도출하는 것을 말한다. - 여기서 Greedy을 직역하면 '탐욕'을 뜻한다. - 왜 '탐욕'이라는 말을 쓸까? 그건 지금 이 순간의 부분적인 최적해가 항상 종합적인 최적해는 아닐 수 있음에도, 욕심쟁이와 같이 지금 보는 이 부분적인 선택이 전체의 최선이라 단정짓기 때문이다. rf. 여러 개의 도시가 연결된 도로가 있고, 그 도로 간에 이동 거리가 각각 다른 상황에서 가장 이동거리가 짧은 거리를 찾아야한다고 할 때, 그리디를 쓰면 가장 짧은 도로들을 선택하는 게 될 수 있다. - 정확함 보다는 적당히 맞는 답을 찾을 때 좋은 알고리즘이다. 따라서, 그리디 알고리즘을 근사 알고리즘으로도 부른다. - 언..

[알고리즘] 탐색 - DFS, BFS, 이진 탐색

| 탐색이란? 주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘 | 탐색의 종류 언제? 특징 시간복잡도 DFS(깊이 우선 탐색) 그래프의 모든 노드를 탐색하고자 할 때 - 재귀 또는 스택을 통해 구현 - 트리의 pre-order, in-order, post-order 순회 모두 DFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) BFS(너비 우선 탐색) 그래프의 가까운 지점부터 탐색하고자 할 때 - 큐를 통해서 구현 - 트리의 level-order 가 BFS이다. * 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) 이진 탐색 * DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다. 1. DFS (깊이 우선 탐색) DFS란, 루트에서 시작..

HashSet<int[]>와 Hashset<ArrayList<Integer>>

| HashSet와 Hashset 문제를 풀다보면, 좌표를 집합에 넣어야 하는 경우가 있었다. 예를 들어, (0, 1), (2, 1) 그래서 아무 생각 없이 아래와 HashSet를 쓰게 되면 contains를 할 때 검색이 제대로 되지 않는 걸 볼 수 있다. 왜 그럴까? 이유는 배열의 경우 Hashcode를 비교하고, 리스트의 경우 Wrapper된 Integer값을 비교하기 때문. HashSet int 배열의 hashcode를 비교 HashSet Integer List의 Wrapper객체(Integer)를 비교 따라서, 좌표와 같은 수열의 집합을 만든다고 하면 HashSet 안에 ArrayList로 넣는 것이 좋다. [ 참고 ] https://stackoverflow.com/questions/654546..

[알고리즘] 정렬

| 정렬이란 - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법 - 기본 : 버블, 삽입, 선택 - 비교적 속도가 빠른 정렬 : 합병, 힙, 퀵, 트리 - 하이브리드 정렬 : 팀, 블록병합, 인트로 - 기타 : 기수, 계수(카운팅), 셸, 보고 | 정렬의 시간복잡도 요약 - 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때, 같은 숫자 1에 대해서 { 1, 1, 1, 1 } 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다. - 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데, 버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다. 정렬 방법 시간 복잡도 보조 메모리 안정성 Ω(n) Θ(..

[알고리즘] 알고리즘 개요

| 알고리즘이란? 알고리즘이란, 어떤 문제를 해결하기 위한 절차나 방법을 말한다. - 알고리즘의 조건 입력 데이터의 입력 출력 처리 후 출력 명확성 동작의 흐름(flow)에 대한 명확성 유한성 정해진 시간 및 공간 내에서의 처리 효율성 같은 동작을 하더라도 시간 및 공간 면에서 보다 효율적이어야 한다. | 알고리즘은 결국 정확성과 시간 복잡도, 공간 복잡도를 말한다. - 어떻게 보다 적은 자원을 효과적으로, 정확하게 만들어 내느냐가 알고리즘의 핵심 | 알고리즘 정리 개요 - 앞으로 정리할 알고리즘 목록입니다. - (글 작성 후 링크 업로드 예정) 정렬 이진탐색 / 투 포인터 그리디 알고리즘 분할 정복 / 다이나믹 프로그래밍 백 트래킹 최단 경로 최소 신장 트리 [ 참고 및 출처 ] 부트 캠프 강의를 들은..

[백준 11660] 구간 합 구하기 5

| 시작하기 전에 지난번에는 일차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루었다면, 이번에는 이차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루어보았다. 🔖 일차원 구간합에 대한 포스팅은 아래에 [백준 11659] 구간합 🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N why-dev.tistory.com 🛎 11660 구간 합 구하기 5 | 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N ..

[백준 17609] 회문 (팰린드롬)

팰린드롬이란, 앞 뒤가 똑같은 전화번호 문자열을 말한다고 합니다. 단순히 "abba" 문자열이 팰린드롬인가를 확인한다면, [1] 문자열을 거꾸로 뒤집어서 확인하거나 [2] 양끝에 left, right로 커서를 두고 left < right 일때까지 양 끝을 비교해도 되는데요. 물론 우리의 알고리즘은 그렇게로만 끝나지 않기 때문에 더 향상된 버전의 팰린드롬을 만날 수 있었습니다. 제 수준에서 풀만한 것들을 먼저 뽑아보았어요.. 아래 중에서 하나씩 풀어보려 합니다. | 백준 팰린드롬 문제 모음 브론즈 1259 팰린드롬수 바로가기 실버 1213 팰린드롬 만들기 1254 팰린드롬 만들기 17609 회문 바로가기 바로가기 바로가기 골드 1053 팰린드롬 공장 바로가기 🛎 17609 회문 | 문제 회문(回文) 또는 ..

[백준 10434] 행복한 소수 - 소수 구하기 + 행복한 수

행복한 수에 대한 연습문제를 풀다가, 백준에 관련된 문제가 있나 싶어 찾아보았습니다. 행복한 수만 구하는 문제는 아니고, 행복한 소수를 구하는 문제가 있었어요. 그래서 한 번 개념 정리를 먼저 하고 문제를 풀어보고 정리를 하려 합니다. | 행복한 수란? 십진수의 수가 있을 때, 예를 들어 14가 있다고 할 때, 각 자릿수를 제곱한 합은 1^2 + 4^2 = 18 입니다. 다시 29의 각 자릿수를 제곱한 합을 구하면 1^2 + 8^2 = 65 이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요. - 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면, - 어떤 수는 제곱합의 끝이 1이 되면..

[백준 11659] 구간합

🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. | 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. | 예제 입력 5 3 5 4 3 2 1 1 3 2 4 5 5 | 예제 출력 12 9 1 🔎 문제분석 이 문제를 반복문으로 풀려고 했을 때, 계속적으로 시간초과가 나타났다. 입출력을 내가 아는 모든 방법을 총동원해서 변경해보았지만 역부족. '뭐지, 풀 수 없는 문제인가' 했었는데,..

[백준 2231] 분해합

🛎 2231 분해합 | 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. | 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. | 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. | 예제 입력 216 | 예제 출력 198 🔎 문제분석 어떤 ..