알고리즘 풀이(Problem Solving) 검색 결과

해당 글 150건

알고리즘 풀이 - 백준 1285(동전 뒤집기, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxN 행렬로 동전이 앞 뒤로 놓여 있는 경우 1회 연산에 1행 또는 1열의 N개 동전을 모두 뒤집을 수 있을 때, 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제 2. 풀이 각 동전은 행 또는 열을 바꿀 때, 그 결과가 바뀔 수 있다. 즉, 모든 동전은 2번의 변환이 가능하다. 따라서 접근 방식은 다음과 같다. 3x3 크기의 행렬로 동전이 있다고 가정하자. 그러면, 행을 바꾸는 경우는 아래와 같이 총 7가지가 있다. ① 모든 행을 바꾸지 않는 1가지 ② 모든 행을 다 바꾸는 1가지 ③ 2개의 행을 골라 바꾸는 3가지 ④ 1개의 행을 골라 바꾸..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 22:56

알고리즘 풀이 - 백준 2138(전구와 스위치, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 스위치와 전구가 있을 때, 각 전구는 켜지거나(1) 꺼지거나(0)의 2가지 상태를 가지고 스위치를 누르면 자기 자신과 양 옆 스위치의 상태가 변할 때, N개의 전구를 특정 상태로 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구하는 문제 2. 풀이 행렬 관련 문제와 유사하다.(관련 포스팅은 여기) 각 전구는 켜지거나 꺼지거나의 경우 뿐이므로 좌측 부터 체크하여 목표 상태와 값이 다른 경우 스위치를 눌러 주는 방식으로 해결이 가능하다. 그런데, 이 문제에서는 스위치를 누르면 자신 보다 좌측(이전) 위치에 있던 전구 또한 영향을 받기 때문에 가장 좌측의 있는 전구..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 22:27

알고리즘 풀이 - 백준 1080(행렬, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0 또는 1로만 이루어진 행렬 A, B가 있을 때, A를 B로 바꾸는 데 필요한 최소 연산의 횟수를 구하는 문제로, 연산은 전체 행렬의 3x3의 부분 행렬을 0이면 1로, 1이면 0으로 모두 바꾸는 것이다. 2. 풀이 각 행 / 열의 모든 위치는 0 또는 1이다. 즉, 기존에 1이었다면 바꾸거나 바꾸지 않거나의 경우로 나뉠 수 있다. 접근 방법은 다음과 같다. 우리는 A → B 행렬로 무조건 변환해야 한다. 따라서 최소의 연산을 통해 변환하려면 서로 다른 부분이 있는 경우에만 연산을 수행하면 된다. 예를 들어 5x5 크기의 A 행렬이 있다고 가정하자. 그러면 각 행/..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 21:59

알고리즘 풀이 - 백준 11399(ATM, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1대의 ATM에 N명의 사람이 줄을 섰을 때, m번째 사람이 돈을 인출 시 걸리는 시간은 Pm이라고 하면 모든 사람이 대기 시간을 합쳐 모두 돈을 인출 시에 걸리는 최소의 시간을 구하는 문제 2. 풀이 이 문제는 그리디로 해결 가능한 제일 쉬운 수준의 문제이다. 전체 대기 + 인출까지 모든 인원이 수행할 수 있도록 합이 최소가 되려면 뒤의 사람이 걸리는 시간이 최소가 되어야만 한다. 예를 들어 아래를 보자. 인원이 3명이 있을 때, 각 인원이 인출 시 걸리는 시간은 다음과 같다. 사람 3명 - 10, 6, 4 그러면, 오래 걸리는 사람이 앞에 있으면 뒤의 사람들은 대..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 11. 15:45

알고리즘 풀이 - 백준 1931(회의실 배정, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 회의실이 1개일 때, N개 회의에 대한 사용표를 만들고자 한다. 회의의 시작/종료 시간이 주어질 때, 겹치지 않도록 회의실을 쓰는 최대 회의의 수를 구하는 문제 2. 풀이 이 문제는 대표적인 그리디 알고리즘으로 해결 가능한 활동 선택(Action Selection) 문제이다. 최대한 많은 회의를 수행하기 위해서는 끝나는 시간을 기준으로 정렬을 수행하면 된다. 왜냐하면, 무조건 일찍 끝나는 회의를 우선 수행한 뒤, 다음 회의들을 수행하면 가장 최대의 회의를 진행할 수 있기 때문이다. 즉, 시간이 겹치지만 않는다면 무조건 더 빠르게 끝나는 회의를 우선적으로 수행하고 이후..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 11. 15:23

알고리즘 풀이 - 백준 11047(동전 0, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 서로 다른 종류의 동전으로 K라는 숫자를 만들 수 있을 때, 최소의 개수로 만드는 경우의 수를 구하는 문제 2. 풀이 이 문제는 대표적인 쉬운 그리디 알고리즘으로 풀 수 있는 문제이다. 동전들이 N개 있을 때, $A_n 은 A_{n-1}$의 배수이기 때문에 동일한 숫자를 큰 단위의 동전으로 만드는 것은 작은 동전으로 만드는 경우보다 무조건 더 적은 수의 동전이 필요하다. 예를 들어, 1,000을 만들고 싶을 때, 동전이 2가지가 있는데 각 동전이 500, 1000원 짜리라고 생각해보자. 이 경우에 1,000원 짜리 동전은 1개면 되지만 500원짜리 동전은 2개..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 11. 14:33

알고리즘 풀이 - 백준 14395(4연산, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 4개의 연산으로 A → B로 변환 가능한 최소의 연산의 경우를 사전 순으로 가장 앞서는 1개만 출력하는 문제 2. 풀이 각 연산은 다음과 같다. ① * 연산 : S = S*S ② + 연산 : S = S + S = 2xS ③ - 연산 : S = S - S = 0 ④ / 연산 : S = S / S = 1 여기서 처음에 단순 BFS로 모든 숫자를 탐색하여 가능한 연산 중 가장 적은 방식으로 연산하는 경우를 찾고자 할 수 있다. 그러나 다시 문제를 보면 최대 탐색 가능 숫자가 $10^9$이다. 즉, 10억이다.. 그..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 23:05

알고리즘 풀이 - 백준 10026(적록색약, 그래프(BFS, DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxN크기의 그리드에 색상이 표시되어 있을 때, 적록색약의 경우와 일반인의 경우에 구분 가능한 색상 구역의 개수를 구하는 문제 2. 풀이 가장 기초적인 수준의 그래프 탐색 문제이다. 일반인의 경우와 적록색약인 경우에 그리드를 별도로 저장하여 각각 BFS를 수행한 뒤 구역의 개수를 구하는 방식으로 문제를 해결하였다. 3. 코드 아래의 코드를 통해 정답을 알아보자. ① BFS로 풀기 import java.io.*; import java.util.*; public class Main{ static int n; st..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:54