알고리즘공부(Algorithm Study)78

• 

  비트연산과 2의 보수: 기본 개념부터 실습까지 완벽 가이드 1. 비트연산이란?비트연산은 컴퓨터에서 데이터를 처리할 때 사용하는 기본적인 연산 방식입니다. 데이터가 이진수(0과 1)로 표현되기 때문에, 이러한 비트를 조작하는 것이 중요합니다. 비트연산은 보통 프로세서의 수준에서 매우 빠르게 처리되며, 효율적인 프로그램 작성에 필수적인 요소입니다.2. 비트연산의 주요 종류비트연산에는 여러 가지 종류가 있으며, 각 연산은 특정 비트 패턴을 조작하는 데 사용됩니다.AND 연산: 두 비트가 모두 1일 때만 1을 반환합니다.OR 연산: 두 비트 중 하나라도 1이면 1을 반환합니다.NOT 연산: 비트를 반전시킵니다. 0은 1로, 1은 0으로 바뀝니다.XOR 연산: 두 비트가 다를 때 1을 반환합니다.이러한 비트연산은 주로 마스크(mask)를 사용하여 특정 비트를 선택하거나 .. 알고리즘공부(Algorithm Study) 2024. 8. 16.

• 

  Karatsuba 알고리즘 Karatsuba 알고리즘이란?Karatsuba 알고리즘은 큰 수의 곱셈을 더 효율적으로 수행하기 위한 알고리즘입니다. 이 알고리즘은 1960년에 안넨카롤로스 Karatsuba에 의해 처음 개발되었으며, 전통적인 곱셈 방법보다 계산 복잡도가 낮습니다.1. 전통적인 곱셈의 문제점일반적으로 두 자리수가 각각 n자리수일 때, 이들을 곱하기 위해서는 O(n^2)의 시간이 소요됩니다. 예를 들어, 두 개의 4자리수를 곱할 때는 각 자리수마다 곱셈과 덧셈을 반복하는 방식으로 총 16번의 곱셈을 수행하게 됩니다. 이 방식은 숫자가 커질수록 연산량이 급격히 증가하여 비효율적입니다.2. Karatsuba 알고리즘의 기본 개념Karatsuba 알고리즘은 '분할 정복(Divide and Conquer)' 접근 방식을 사용하.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2024. 8. 13.

• 

  무한히 큰 수 두 개의 사칙연산 처리 방법과 파이썬 예제 무한히 큰 수를 다루는 것은 암호화, 금융 계산, 과학적 시뮬레이션 등 여러 분야에서 중요한 역할을 합니다. 하지만 단순히 큰 수의 사칙연산을 처리하는 것뿐만 아니라, 이러한 연산을 효율적으로 수행하는 알고리즘과 방법이 필요합니다. 이 글에서는 무한히 큰 수를 다루는 방법과 효율적인 사칙연산 알고리즘을 소개하고, 파이썬 예제 코드도 함께 살펴보겠습니다.1. 무한히 큰 수의 개념무한히 큰 수는 컴퓨터의 기본 데이터 타입으로 표현할 수 없는 크기의 숫자를 의미합니다. 컴퓨터에서는 메모리와 시간 복잡도 제한 때문에 무한히 큰 수를 다루기 위해서는 특별한 방법이 필요합니다. 특히, 단순한 연산 이상의 복잡한 알고리즘이 필요할 때가 많습니다.2. 무한히 큰 수의 사칙연산 처리무한히 큰 수의 사칙연산은 기본적인 덧.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2024. 8. 13.

• 

  [순열 사이클 분할] 백준 10451 순열 사이클 이번 포스트에서는 백준 10451번 문제인 "순열 사이클"을 파이썬으로 풀이한 방법을 공유하고자 합니다. 이 문제는 주어진 순열 내에서 사이클이 몇 개 존재하는지를 찾는 문제로, DFS(깊이 우선 탐색)를 활용하여 해결할 수 있습니다.순열 사이클 분할 설명순열 사이클 분할은 주어진 순열을 사이클 구조로 분해하는 과정입니다. 순열은 각 요소가 다른 요소로 매핑되는 일종의 함수입니다. 이때, 순환 구조(사이클)를 찾는다는 것은 해당 순열 내에서 자기 자신으로 돌아오는 경로를 찾는 것을 의미합니다.예를 들어, 순열이 다음과 같이 주어졌다고 가정합니다:( \text{순열} = [2, 3, 1, 5, 6, 4] )이 순열에서 사이클을 찾아보면:1 → 2 → 3 → 1 (사이클 형성)4 → 5 → 6 → 4 (사이.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [다익스트라] 백준 1753 최단경로 이번 포스팅에서는 백준 1753번 문제를 다익스트라 알고리즘을 활용하여 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 시작점에서 다른 모든 정점으로 가는 최단 경로를 찾는 문제로, 그래프 이론에서 자주 등장하는 문제 유형입니다.문제 설명주어진 그래프에서 시작점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 그래프는 방향성이 있으며, 간선마다 가중치가 부여되어 있습니다. 다익스트라 알고리즘은 이와 같은 가중 그래프에서의 최단 경로 문제를 효율적으로 해결할 수 있는 알고리즘입니다.다익스트라 알고리즘 개요다익스트라 알고리즘은 그래프 이론에서 가장 널리 사용되는 최단 경로 탐색 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서, 하나의 시작 정점으로부터 다른 모든 정점으로 가는 최.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [등차수열] 백준 2108 수들의 합 이번 포스팅에서는 백준 2108번 문제를 효율적으로 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 수 ( N )을 등차수열로 나타낼 수 있는 모든 경우의 수를 구하는 문제입니다. 특히 이 문제는 자기 자신을 포함한 수열을 고려하는 것을 요구합니다.문제 분석주어진 숫자 ( N )을 자기 자신도 포함하여 하나 이상의 자연수로 이루어진 등차수열로 나타낼 수 있는 모든 경우의 수를 찾는 것이 목표입니다. 수열의 길이가 1 이상인 등차수열을 찾는 과정에서 우리는 ( N )의 약수와 관련된 규칙을 활용할 수 있습니다.핵심 개념등차수열이란?: 등차수열은 연속된 수들의 합입니다. 예를 들어, 1, 2, 3, 4, 5는 모두 연속된 수들이므로, 그 합은 15입니다. 이 문제에서는 어떤 수 ( N )을 연속된 자연수들의.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• sys.stdin.readline() vs input() in Python 파이썬에서 입력을 받을 때, 많은 사람들이 input() 함수를 사용합니다. 하지만 알고리즘 문제나 대량의 입력을 다룰 때는 sys.stdin.readline()이 더 효율적인 경우가 많습니다. 이 두 가지 방법의 차이점을 알아보겠습니다.sys.stdin.readline() vs input()1. 속도 차이sys.stdin.readline()은 더 빠른 속도를 제공합니다. 이 함수는 버퍼를 사용하여 입력을 처리하기 때문에, 반복적으로 많은 양의 데이터를 입력받아야 하는 상황에서 훨씬 더 효율적입니다. 반면, input()은 내부적으로 sys.stdin.readline()을 사용하지만, 추가적으로 개행 문자를 제거하는 작업이 포함되어 있어 상대적으로 시간이 더 소요됩니다.2. 입력 처리 방식sys.stdi.. 알고리즘공부(Algorithm Study)/기본개념(Concept) 2024. 8. 9.

• 시간 제한과 메모리 제한 알고리즘 문제에서 시간 제한, 메모리 제한을 반드시 고려해야합니다, 파이썬으로 문제를 풀 때는 다음과 같은 점들을 고려해야 합니다. 1. 시간 복잡도  • 시간 제한이 1초라는 것은 대략적으로 1초 내에 실행될 수 있는 연산의 수를 의미합니다. • 파이썬에서는 일반적으로 초당 약 1억 번(10^8)의 연산을 처리할 수 있다고 추정할 수 있습니다. • 시간 복잡도에 따라 처리할 수 있는 최대 입력 크기는 다음과 같이 예상할 수 있습니다: • O(1): 상수 시간, 입력 크기와 상관없이 즉시 처리 가능 • O(log N): 수백만 이상의 입력도 처리 가능 • O(N): 최대 약 10^7 ~ 10^8 크기의 입력을 처리 가능 • O(N log N): 최대 약 10^6 ~ 10^7 크기의 입력을 처리 가능 • .. 알고리즘공부(Algorithm Study)/기본개념(Concept) 2024. 8. 9.

• [자료구조/큐] 백준 18258 큐2 package 큐덱; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * push * pop * size * empty * front * back * 명령 수 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 18.

• 

  [누적합]백준 25682 체스판 다시 칠하기 2 package 누적합; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class boj_25682_체스판다시칠하기2 { private static int N, M, K, answer; private static String[][] board; private static int[][][] accSum; public static void main(String[] args) throws IOException { // 1. M x N 크기의 2차원 배열 입력 // 2. 검, 흰 두 가지의 색으로 칠해져 있음 // 3. 아무 곳을 기준으로 K x K 만큼 자르기 // 4. 칠해야 하.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 7.

• 백준 16430 제리와 톰 package 단순구현; import java.util.Scanner; public class boj_16430_제리와톰 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); int B = sc.nextInt(); System.out.print(B-A +" " + B); } } 해당 문제는 다른 문제를 풀다가 머리 식힐겸 풀게된 문제인데 문제는 마치 나눗셈을 유도하는 듯 하지만 나누기연산의 개념이 다른 컴퓨터 내부작동 원리를 어떻게 해결할 지 물어보는 문제 같다. 1kg 기준으로 기약분수 꼴로 나눠야 하므로 결국 1 * B - A / B를 묻는 거나 다름이 없기에 B-A와 B를.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 5.

• [큐] 백준 15828 Router package 큐덱; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class boj_15828_Router { private static Queue router; public static void main(String[] args) throws IOException { router = new LinkedList(); int routerSize, packetCount = 0; BufferedReader br = new BufferedReader(new InputStreamReade.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 3.