코딩테스트 필수 알고리즘 및 개념 정리

코딩 테스트를 준비하기 위해 반드시 공부해야 하는 주요 알고리즘을 정리한다. 다음은 주요 알고리즘과 그 개념, 그리고 사용되는 상황에 대한 설명이다.1. 정렬 알고리즘정렬은 데이터를 특정 순서대로 배열하는 작업이다. 대표적인 정렬 알고리즘으로는 버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬, 퀵 정렬 등이 있다. 정렬은 배열을 정리하거나 탐색 효율성을 높이기 위해 사용된다.버블 정렬: 인접한 두 요소를 비교하여 정렬한다. 시간 복잡도는 O(n^2)이다.삽입 정렬: 정렬된 부분과 정렬되지 않은 부분으로 나눠 하나씩 삽입하며 정렬한다. 시간 복잡도는 O(n^2)이다.퀵 정렬: 기준점을 잡고 이를 기준으로 작은 값과 큰 값을 분리하여 재귀적으로 정렬한다. 평균 시간 복잡도는 O(n log n)이다.2. 탐색..

• format_list_bulleted CodingTest/algorithm
• · 2024. 12. 22.
• textsms

[Python] 백준 1463 1로만들기 문제풀이 및 정답코드

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 문제해설이번 문제는 DP의 가장 기본적인 형태의 문제였다.1로 만드는 경우는 총 세가지 존재한다.3으로 나누거나, 2로 나누거나, 1을 빼거나 이 문제를 해결하는 가장 중요한 키포인트는dp를 입력 n의 숫자만큼 만든 뒤,각 숫자를 만드는 데에 걸리는 최소의 연산 횟수를 계..

• format_list_bulleted CodingTest/BOJ
• · 2024. 12. 17.
• textsms

[Python] 백준 1149 RGP거리 문제풀이 및 정답코드

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.  입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다..

• format_list_bulleted CodingTest/BOJ
• · 2024. 12. 16.
• textsms

파이썬에서 stack, queue, linked list 구현하기

파이썬에서 주요 자료구조 사용 및 구현자료구조는 데이터를 효율적으로 저장하고 처리하기 위한 체계이다.이 글에서는 스택, 큐, 연결 리스트와 같은 주요 자료구조를 파이썬에서 구현하는 방법을 알아보자1. 스택(Stack)스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조이다.파이썬에서는 리스트를 사용하여 스택을 구현하거나,collections 모듈의 deque를 사용할 수 있다.1.1 리스트를 사용한 스택 구현stack = []# 스택에 요소 추가 (push)stack.append(10)stack.append(20)stack.append(30)# 스택에서 요소 제거 (pop)element = stack.pop()print("제거된 요소:", element) # 30# 현..

• format_list_bulleted CodingTest/algorithm
• · 2024. 12. 14.
• textsms

10828 백준 스택 - 파이썬

문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.입력첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.문..

• format_list_bulleted CodingTest/BOJ
• · 2024. 12. 11.
• textsms

분할정복 알고리즘 이해하기 - 백준 2630번 색종이 만들기

분할정복 (Divide and Conquer)1. 개요분할정복(Divide and Conquer)은 문제를 해결하는 알고리즘 설계 기법 중 하나이다.문제를 더 작은 하위 문제들로 분할하고,각각의 하위 문제를 해결한 후 그 결과를 합쳐서 원래 문제를 해결하는 방식이다. 이 기법은 주로 재귀적으로 구현되며, 여러 문제에서 효과적인 해결책을 제공한다.대표적인 분할정복 알고리즘의 예로는병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 그리고 이진 탐색(Binary Search)이 있다.2. 분할정복의 단계분할(Divide): 문제를 동일하거나 유사한 하위 문제들로 나눈다.정복(Conquer): 하위 문제들을 재귀적으로 해결한다. 하위 문제가 충분히 작아지면, 직접 해결한다.결합(Combine):..

• format_list_bulleted CodingTest/algorithm
• · 2024. 12. 10.
• textsms