본문 바로가기

개발/CodingTest55

[백준_분할정복] 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.
[자료구조] 퀵 정렬이란? 오늘은 퀵정렬에 대해서 알아보려고 합니다. 선택, 삽입, 퀵 정렬 중에서 퀵 정렬이 가장 많이 사용되는 알고리즘입니다. '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?' 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다. 쿽 정렬에서는 피벗이 사용되는데, 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피펏이라고 표현합니다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 합니다. 퀵 정렬 분할 방식 중에서 호어 분할 방식(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.
[자료구조] DFS 이란? 깊이 우선 탐색 (DFS) 이란? 깊이 우선 탐색(DFS, Depth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 시작 노드에서 출발하여 가능한 한 깊이 들어가서 더 이상 진행할 수 없을 때까지 탐색을 진행한 후, 다음 분기로 넘어가는 방식을 취합니다. DFS의 주요 특징 1. 재귀 또는 스택 사용 DFS는 주로 재귀 함수 호출 또는 스택을 사용하여 구현됩니다. 각 노드를 방문하면 스택에 현재 노드를 추가하고, 더 이상 진행할 수 없을 때 스택에서 이전 노드로 돌아갑니다. 2. 깊이 우선 DFS는 한 분기를 깊이 탐색하며, 더 이상 진행할 수 없을 때까지 계속 진행합니다. 따라서 가장 깊이 있는 노드를 먼저 탐색하고 나중에 돌아옵.. 2024. 1. 23.
[백준] 13305번 - 주유소 - 그리디 알고리즘 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는.. 2024. 1. 22.

티스토리툴바