본문 바로가기

분류 전체보기82

[백준_분할정복] 2740번 - 행렬 곱셈 - 이해까지 도와주는 풀이 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. 입력 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. 출력 첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다. 예제 입력 3 2 1 2 3 4 5 6 2 3 -1 -2 0 0 0 3 예제 출력 -1 -2 6 -3 -6 12 -5 -10 18 풀이 이번 문제는 행렬.. 2024. 1. 27.
[백준_분할정복] 1629번 - 곱셈 - 이해까지 도와주는 풀이 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입력 10 11 12 예제 출력 4 풀이 이 문제는 지수가 짝수인 경우와 홀수인 경우를 나눠서 풀 수 있습니다. 지수가 짝수인 경우 만약 b가 짝수라면, half_power에는 power_mod(a, b //2 , c)를 호출하여 a를 b의 절반으로 제곱한 결과를 저장합니다. 그리고 나서 (half_power * half_power) % c 를 계산하여 .. 2024. 1. 27.
[백준] 1780번 - 종이의 개수 - 이해까지 도와주는 풀이 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출력 첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 .. 2024. 1. 27.
[백준] 2630번 - 색종이 만들기 - 이해까지 도와주는 풀이 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의.. 2024. 1. 27.
[주식] 테슬라를 예시로 최적의 매수 타점 찾기 및 물타기법 안녕하세요. 오늘은 주식투자를 하실 때, 더 빠질 수 있는 가능성이 열려 있는 상태에서 주식을 사거나, 물을 타는 비극적인 일을 방지하고자 어떻게 하면 최적이 타이밍에 주식을 분할 매수, 분할 물타기 할 수 있을 지 알아보도록 하겠습니다. 이번 게시물에 활용한 차트는 테슬라입니다. 테슬라 주주분들에게 도움이 되었으면 좋겠습니다. 우리는 금융전문가처럼 수백권의 책과 통계적 수학 공식, 경제적 전문 지식을 가지고 있지 않습니다. 그런 지식들을 습득하고 투자를 하기에는 우리는 시간이 많지 않습니다. 그래서 저는 이미 어느정도 입증된 지표나 판단 기준을 참고하여, 최소한 우리가 뇌동매매로 잘못된 타이밍에 주식을 하는 일을 방지하는 것이 최선의 방법이라고 생각합니다. 그렇다고 단순히 하나의 지표만 가지고 매수타이.. 2024. 1. 26.
[자료구조] 퀵 정렬이란? 오늘은 퀵정렬에 대해서 알아보려고 합니다. 선택, 삽입, 퀵 정렬 중에서 퀵 정렬이 가장 많이 사용되는 알고리즘입니다. '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?' 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다. 쿽 정렬에서는 피벗이 사용되는데, 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피펏이라고 표현합니다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 합니다. 퀵 정렬 분할 방식 중에서 호어 분할 방식(Hoare Partition Scheme)을 사용하면서 리스트를 두 부분으로 나누고, 각 부분을 재귀적으로 정렬합니다. 아래는 주어진 리스트를 사용하여 .. 2024. 1. 24.
[자료구조] 삽입정렬이란? 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편입니다. 그렇다면 다른 접근 방법에 대해서 생각해볼 필요성이 있습니다. 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까? 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때, 훨씬 효율적으로 작동합니다. 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 부릅니다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위에 삽입된다는 점이 특징입니다. 소스 코드로 보시면 이해가 수월하실 것입니다. 소스코드 # 삽입정렬 array = [7,5,9,0.. 2024. 1. 24.
[자료구조] 선택정렬이란? 선택정렬 오늘은 정렬 중에서 가장 쉬운 정렬, 선택정렬에 대해서 얘기해보려고합니다. 선택정렬이란, 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 테이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 말합니다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어집니다. 바로 소스코드로 보시는 것이 이해하기 수월하실 겁니다. 소스 코드 # 선택정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): # 일단 첫번째 숫자를 가장 작은 숫자라고 가정 min_index = i # 뒤에 숫자들과 비료하면서 크기 비교 for j in rang.. 2024. 1. 24.
[자료구조] DFS와 BFS의 비교 DFS vs. BFS: 그래프 탐색 알고리즘 비교 그래프 탐색은 그래프나 트리와 같은 자료구조에서 노드를 탐색하는 중요한 작업입니다. 이러한 탐색을 수행하기 위해 주로 사용되는 두 가지 알고리즘인 "깊이 우선 탐색 (DFS)"와 "너비 우선 탐색 (BFS)"를 비교해보겠습니다. [자료구조] DFS 이란? 깊이 우선 탐색 (DFS) 이란? 깊이 우선 탐색(DFS, Depth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 시작 노드에서 출발하여 가능한 sonlife97.tistory.com [자료구조] BFS 이란? 너비 우선 탐색 (BFS) 이란? 너비 우선 탐색(BFS, Breadth-First Search)은 그래프와 트리와 같은.. 2024. 1. 23.
[자료구조] BFS 이란? 너비 우선 탐색 (BFS) 이란? 너비 우선 탐색(BFS, Breadth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 시작 노드에서부터 인접한 모든 노드를 먼저 탐색하고, 그 다음 레벨의 노드로 넘어가며 탐색을 진행합니다. 즉, 깊이보다 너비를 우선으로 탐색하는 방식입니다. BFS의 주요 특징 1. 큐(queue) 사용 BFS는 큐 자료구조를 사용하여 구현됩니다. 시작 노드를 큐에 넣고, 큐가 빌 때까지 노드를 하나씩 빼면서 탐색을 진행합니다. 2. 너비 우선 BFS는 한 레벨의 모든 노드를 먼저 탐색하며, 그 다음 레벨로 넘어갑니다. 따라서 가장 가까운 노드부터 탐색하여 최단 경로 문제에 유용하게 사용됩니다. 3. 모든 노드 탐색 B.. 2024. 1. 23.

티스토리툴바