티스토리

공부하게 성실하자

검색하기

블로그 홈

공부하게 성실하자

coder-areum.tistory.com/m

모닝펄슨 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

정렬 알고리즘 class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; // 선택 정렬 for (int i = 0; i arr[j]) { minIdx = j; } } // 스와프 int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } // 삽입 정렬 for (int i = 1; .. 공감수 0 댓글수 0 2025. 3. 4.
[백준] 인구 이동 문제https://www.acmicpc.net/problem/16234 풀이이 문제 풀이의 핵심은 모든 좌표에 대해서 BFS/DFS를 수행해야 한다는 것이다. 연결되어 있지 않은 나라도 있을 수 있기 때문이다. 내가 처음에 풀었던 풀이에서부터 다음과 같은 오류들을 수정하였다. 모든 좌표에 대해 BFS 수행해야 한다.BFS 시작 시 첫 나라의 인구도 포함해야 한다.연합이 2개 이상이면 인구 이동을 수행한다.이동이 발생했는지 체크하고 반복을 결정한다. import java.util.*;class Main { static int n, l, r; static int[][] A; static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, .. 공감수 0 댓글수 0 2025. 2. 28.
[백준] 감시 피하기 문제https://www.acmicpc.net/problem/18428 풀이 문제 요약NxN 크기의 복도에서 선생님(T), 학생(S), 장애물(O), 빈칸(X)이 주어진다.선생님은 상, 하, 좌, 우 방향으로 감시를 하며, 장애물이 있으면 그 뒤는 볼 수 없다.학생들이 선생님의 감시를 피할 수 있도록 정확히 3개의 장애물을 배치할 수 있는지 확인해야 한다.가능한 모든 장애물 배치 경우의 수를 확인하고, 학생이 들키지 않는 경우가 존재하는지 판단해야 한다. import java.util.*;class Combination { // nCr 조합 구하는 로직 private int n; // 전체 요소 개수 private int r; // 뽑을 요소 개수 private int[] now.. 공감수 0 댓글수 0 2025. 2. 27.
[백준] 연산자 끼워넣기 문제https://www.acmicpc.net/problem/14888 풀이입력 처리n개의 숫자를 입력받고, 리스트 arr에 저장.덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 입력받음.DFS(백트래킹) 활용dfs(i, now): 현재 i번째 숫자를 처리 중이고, now는 현재까지 계산된 값.모든 숫자를 처리하면 minValue, maxValue 갱신.남아있는 연산자를 하나씩 사용하면서 백트래킹 수행.연산 적용 방식덧셈, 뺄셈, 곱셈, 나눗셈 연산자가 남아있다면 사용 후 dfs 재귀 호출.연산 후에는 원상 복구하여 다른 경우의 수를 탐색할 수 있도록 함.결과 출력maxValue: 가능한 수식 중 가장 큰 값.minValue: 가능한 수식 중 가장 작은 값. import java.util.*;publi.. 공감수 0 댓글수 0 2025. 2. 25.
[프로그래머스] 괄호 변환 문제https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이빈 문자열이면 그대로 반환.p를 균형잡힌 괄호 문자열 u와 v로 분리.u가 올바른 괄호 문자열이면, v를 재귀적으로 변환 후 u + solution(v) 반환.u가 올바른 문자열이 아니라면( 를 추가하고 solution(v) 결과를 붙이고 ) 추가.u의 앞뒤 문자를 제거하고 괄호 방향을 반대로 변환하여 붙임.변환된 문자열을 반환. class Solution { // 균형잡힌 문자열의 인덱스 반환 public int bal.. 공감수 0 댓글수 0 2025. 2. 25.
[백준] 경쟁적 전염 [문제]https://www.acmicpc.net/problem/18405 [풀이]import java.util.*;class Virus implements Comparable { private int index; private int second; private int x; private int y; public Virus(int index, int second, int x, int y) { this.index = index; this.second = second; this.x = x; this.y = y; } public int getIndex() { return index; } pub.. 공감수 0 댓글수 0 2025. 2. 24.
[백준] 연구소 문제https://www.acmicpc.net/problem/14502 정답나는 완전 탐색을 이용해서 벽을 세울 수 있는 경우의 수를 구했는데 DFS/BFS를 통해서도 구할 수 있는 모양이다.풀이 방식은 다음과 같다.벽 3개를 세울 수 있는 경우의 수 다 세워보기벽이 세워진 후 바이러스 퍼지게 하기바이러스 퍼진 후 안전 영역 개수 세기안전 영역이 최댓값일 때를 저장해서 출력하기 [내 풀이]import java.util.*;public class Main { private static int[][] lab; private static int N, M; public static int BFS() { Queue queue = new LinkedList(); int.. 공감수 0 댓글수 0 2025. 2. 24.
[백준] 특정 거리의 도시 찾기 문제https://www.acmicpc.net/problem/18352 그래프를 표현하는 방법에는 두 가지가 있다. 1. 인접 행렬 (Adjacency Matrix)N x N 크기의 2차원 배열 사용 (int[][] graph = new int[N][N])graph[A][B] = 1 이면 A -> B로 가는 간선이 존재간선이 없으면 0으로 저장 2. 인접 리스트 (Adjacency List)리스트 배열 또는 리스트의 리스트 사용 (List> graph)graph[A] 리스트에 B를 저장하면 A -> B로 가는 간선이 존재 이 문제는 인접 행렬이 더 적합한데, N이 100,000개만 되어도 100,000 x 100,000 = 10,000,000,000 (100억 개) 크기의 배열이 필요하게 되기 때문이.. 공감수 0 댓글수 0 2025. 2. 24.
[프로그래머스] 외벽 점검 문제https://school.programmers.co.kr/learn/courses/30/lessons/60062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 코드import java.util.*;class Permutation { private int n; private int r; private int[] now; // 현재 순열 private ArrayList> result; // 모든 순열 public ArrayList> getResult() { return result; } public Permutation(int n, int .. 공감수 0 댓글수 0 2025. 2. 22.
플로이드-워셜 플로이드-워셜 (floyd-warshall)그래프에서 최단 거리를 구하는 알고리즘. 주요 특징은 다음과 같다. 기능특징시간 복잡도 (노드 수: V)모든 노드 간에 최단 경로 탐색- 음수 가중치 에지가 있어도 수행할 수 있음.- 동적 계획법의 원리를 이용해 알고리즘에 접근O(V^3) 플로이드-워셜의 핵심 이론플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 색칠된 에지 경로가 1 -> 5 최단 경로라면 1 -> 4 최단 경로와 4 -> 5 최단 경로 역시 색칠된 에지로 이뤄질 수밖에 없다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으.. 공감수 0 댓글수 0 2024. 6. 21.
벨만-포드 벨만-포드(bellman-ford-moore)그래프에서 최단 거리를 구하는 알고리즘은 다익스트라, 벨만-포드, 플로이드 워셜이 있다. 특정 시작점에서 다른 모든 노드로의 최단 거리를 구하는 알고리즘은 다익스트라, 벨만-포드이고, 그 중 음수 간선을 다루는 유일한 알고리즘이 바로 벨만-포드이다. 그래서 코딩 테스트에서 벨만-포드가 나온다면 최단 거리보단 음수 사이클이 있는지 판단하는 문제가 더 많이 나오게 된다. 벨만-포드의 주요 특징은 다음과 같다. 기능특징시간 복잡도(노드 수:V, 에지 수:E)특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색- 음수 가중치 에지가 있어도 수행할 수 있음- 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음O(VE) 벨만-포드의 핵심 이론1. 에지 리스트.. 공감수 1 댓글수 2 2024. 6. 21.
다익스트라 다익스트라 (Dijkstra)다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다. 기능특징시간 복잡도 (노드 수 : V, 에지 수: E)출발 노드와 모든 노드 간의 최단 거리 탐색에지는 모든 양수O(ElogV) 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다. 다익스트라 알고리즘의 핵심 이론1. 인접 리스트로 그래프 구현하기 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결했다. 2. 최단 거리 배열 초기화하기최단 거리 배열을 만들고,.. 공감수 0 댓글수 1 2024. 6. 15.
위상 정렬 위상 정렬 (topology sort)위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 기능특징시간 복잡도(노드 수 :V, 에지 수 :E)노드 간의 순서를 결정사이클이 없어야 함O(V+E) (참고 : https://m.blog.naver.com/ndb796/221236874984) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다. 위상 정렬의 핵심 이론위상 정렬은 다음과 같은 단계로 설명할 수 있다. 다음 예를 보자. 위상 정렬의 원리 이해하기1. 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다. 다음을 보면 ArrayList로 그래프를 표현했다. 그래프.. 공감수 0 댓글수 1 2024. 6. 11.
유니온 파인드 유니온 파인드 (union-find)유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/ 유니온 파인드(Union-Find)유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.. 공감수 0 댓글수 0 2024. 6. 7.
그래프의 표현 그래프그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다. 여기서는 그래프를 구현하는 3가지 방법을 알아본다. 에지 리스트 (edge list)에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다. 에지 리스트로 가중치 없는 그래프 표현하기가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. 노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer 형이다.1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한.. 공감수 0 댓글수 1 2024. 6. 4.
정수론 - 확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명한다. 확장 유클리드 호제법의 핵심 이론확장 유클리드 호제법에서 해를 구하고자 하는 방정식은 다음과 같다. 해를 구하고자 하는 방정식ax + by = c (a, b, c, x, y는 정수) 이때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가진다. 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 의미한다.. 공감수 0 댓글수 0 2024. 6. 1.
정수론 - 유클리드 호제법 유클리드 호제법 (euclidean-algorithm)유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다. 유클리드 호제법의 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다. 연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 // 10 % 4 = 2 MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.앞 단계에서의 작은 수와 MOD 연산 결괏.. 공감수 0 댓글수 0 2024. 5. 31.
정수론 - 오일러 피 오일러 피오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만 여기서는 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아본다. 오일러 피의 핵심 이론오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다.2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] / K 연산을 수행한다. (i는 K의 배수)3. 배열의 끝까지 2를 반복하며 오일러 피 함수를 완성한다. 오일러 피 함수의 원리 이해하기 1. 구하고자 하는 범위까지 배열을 생성.. 공감수 0 댓글수 0 2024. 5. 30.
정수론 - 소수 구하기 수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻한다. 실제 코딩 테스트에서는 모든 정수론의 분야가 나오지 않고, 영역도 매우 방대하므로 전체를 공부하기에는 효율성이 떨어진다. 따라서 여기서는 소수 부분과 호제법 부분을 집중적으로 다루도록 하겠다. 소수 구하기소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다. 소수 구하기의 핵심 이론소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 원리는 다음과 같다. 1. 구하고자 하는 소수의 범위만큼 1차원 배열을.. 공감수 1 댓글수 1 2024. 5. 29.
그리디 그리디 (Greedy)그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점도 있다. 그래서 코딩 테스트에서 그리디 알고리즘을 사용하기 전에는 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살펴야 한다. 그리디 알고리즘의 핵심 이론그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다. 그리디 알고리즘 수행 과정1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.2. 적절성 검사 : 현재 선.. 공감수 0 댓글수 0 2024. 5. 28.
이진 탐색 (Binary Search) 이진 탐색 (Binary Search)데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 기능특징시간 복잡도타깃 데이터 탐색중앙값 비교를 통한 대상 축소 방식O(logN) 이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다. 핵심 이론이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다. (내림차순이라면 조건 반대로) 이진 탐색 과정1. 현재 데이터셋의 중앙값(median)을 선택한다.2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로.. 공감수 0 댓글수 0 2024. 5. 25.
너비 우선 탐색 (BFS) 너비 우선 탐색 (BFS, breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 기능특징시간 복잡도 (노드 수: V, 에지 수: E)그래프 완전 탐색- FIFO 탐색- Queue 자료구조 이용O(V+E) 너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다. 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.DFS.. 공감수 0 댓글수 0 2024. 5. 24.
깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS: depth-first search)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능특징시간 복잡도 (노드 수: V, 에지 수: E)그래프 완전 탐색- 재귀 함수로 표현- 스택 자료구조 이용O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 사용하기 때문에 스택 오버플로에 유의해야 한다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다. 핵심 이론1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기DFS를 위해 필요한 초기 작업은 인접 리.. 공감수 0 댓글수 0 2024. 5. 23.
기수 정렬 (Radix sort) 기수 정렬 (Radix Sort)기수 정렬은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.(예를 들어 234, 123을 비교하면 4와 3, 2과 2, 2와 1만 비교한다.) 기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다. 수행 방식은 다음과 같다.일의 자릿수 기준으로 배열 원소를 큐에 집어넣는다. 0번째 큐부터 9번째 큐까지 차례대로 pop을 진행하면 1의 자릿수에 맞게 정렬이 된다. 이어서 십의 자릿수를 기준으로 같은 과정을 진행한다. 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다. 기수 정렬은 O(kn)으로 시간 복잡도가 가.. 공감수 0 댓글수 0 2024. 5. 21.
병합 정렬 (Merge sort) 병합 정렬 (Merge Sort)병합 정렬은 분할 정복 (divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도 평균값은 O(nlogn)이다. 그룹을 병합하는 방법은 투 포인터 개념을 사용하여 왼쪽 포인터와 오른쪽 포인터의 값을 비교하고 작은 값을 결과 배열에 추가한 후 포인터를 오른쪽으로 1칸 이동시키면 된다. 위의 예로 보면, [27, 38] 과 [10, 43] 을 병합해야 할 때 data 1 index와 data 2 index를 둔 후 index1은 첫 배열의 첫 번째 요소를, index2는 두 번째 배열의 첫 번째 요소를 가리킨 후 값을 비교한다. 27과 10중에 10이 더 작으므로 이를 새로운 배열의 첫 번째 .. 공감수 0 댓글수 0 2024. 5. 21.
퀵 정렬 (Quick sort) 퀵 정렬(Quick Sort)퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균적인 시간 복잡도는 O(nlogn)이다. pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다. 퀵 정렬 과정데이터를 분할하는 pivot 설정pivot 기준 다음 2.1~2.5 과정을 거쳐 데이터를 2개의 집합으로 분리start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start 오른쪽으로 1칸 이동end가 기리키는 데이터가 pivot이 가리키는 데이터보다 크면 end 왼쪽으로 1칸 이동start가 가리키는 데이터가 pivot이.. 공감수 0 댓글수 0 2024. 5. 20.
삽입 정렬 (Insertion sort) 삽입 정렬 (Insertion Sort)삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 평균 시간 복잡도는 O(n^2)으로 느린 편이지만 구현하기가 쉽다. 삽입 정렬 과정1. 현재 index에 있는 데이터 값을 선택한다.2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.3. 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.5. 전체 데이터 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다. 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색(binary search) 등과 같은 탐색 알고리즘을 사용하면 시.. 공감수 0 댓글수 0 2024. 5. 16.
선택 정렬 (Selection sort) 선택 정렬 (Selection Sort)대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다. 원리만 간단히 알아보고 넘어가도록 한다. 선택 정렬은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심이다. 선택 정렬 과정1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.3. 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 .. 공감수 0 댓글수 0 2024. 5. 15.
버블 정렬 (Bubble sort) 버블 정렬 (Bubble Sort)두 인접한 데이터의 크기를 비교해 정렬하는 방법. 간단하게 구현할 수 있지만 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다. 다음 그림과 같이 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 버블 정렬 과정1. 비교 연산이 필요한 루프 범위를 설정한다.2. 인접한 데이터 값을 비교한다.3. swap 조건에 부합하면 swap 연산을 수행한다.4. 루프 범위가 끝날 때까지 2~3을 반복한다.5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.6. 비교 대상이 없을 때까지 1~5를 반복한다. 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다.. 공감수 0 댓글수 0 2024. 5. 15.
스택과 큐 스택 : 깊이 우선 탐색 (DFS:Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통. 큐 : 너비 우선 탐색 (BFS:Breadth First Search)에서 자주 사용 [백준 1874번] 스택 수열https://www.acmicpc.net/problem/1874 스택 연산 수행 방법1. 현재 수열 값 >= 자연수현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.예를 들어 현재 수열 값이 4면 스택에는 1, 2, 3, 4를 push하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나온다.. 공감수 0 댓글수 1 2024. 5. 15.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.