분류 전체보기
-
백준 12931번: 두 배 더하기(Python/Java)Algorithm/Algorithm Problem 2022. 2. 13. 14:00
https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 접근 이런 형식의 문제는 여러 문제들을 통해서 몸소 확인했듯이, 0이 나열된 배열에서 목표 배열까지 만드는 것이 아니라, 목표 배열에서 역으로 연산해 0이 나열된 배열을 만드는 것이 훨씬 좋은 풀이 방법이다. 그렇다면 목표 배열을 기준으로 0으로 이루어진 배열을 만들어보자. 우선 주어진 연산을 반대로 생각해야 한다. 1을 더하는 것은 1을 빼는 것으로, 배열 전체를 2배로 만드는 ..
-
백준 23031번: 으어어... 에이쁠 주세요..(Python/Java)Algorithm/Algorithm Problem 2022. 2. 12. 18:21
https://www.acmicpc.net/problem/23031 23031번: 으어어… 에이쁠 주세요.. 밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비 www.acmicpc.net 접근 다른 알고리즘을 활용할 필요도 없이 조건에 맞춰 구현만 해주면 되기 때문에 특별히 어려운 부분은 없다. 다만 주의할 점이 있다면 대학원 생을 만났을 때와 스위치에 접근했을 때, 동시에 사건이 일어난다면 무조건 스위치 키는 행위가 먼저 일어난다는 부분. 이 부분을 간과하고 순서를 다르게 풀이한다면 한동안 오류에서 헤맬 수 있다. 한 가지 더 체크해야 하는 부분. 내가 현재 위치를 탐색..
-
백준 17939번: Gazzzua(Python/Java)Algorithm/Algorithm Problem 2022. 2. 11. 10:32
https://www.acmicpc.net/problem/17939 17939번: Gazzzua 최대의 수익을 얻으려면, 일단 가격이 1, 5일 때 1개씩 사서 10일 때 샀던 코인 2개를 다 팔고, 이어서 가격이 2일 때 1개를 사고 4일 때 판다. 이 경우, 총 (10-1) + (10-5) + (4-2) = 16의 수익을 얻을 수 있 www.acmicpc.net 접근 실제 가상화폐든, 그리디 알고리즘의 가상화폐든 이득을 얻는 방법은 간단하다. 저점에서 사고 고점에서 파는 것이다. 만고불변의 진리. 그렇다면 이 문제는 어떻게 해결해야 할까? 저점에서 사고 고점에서 팔면 되지!! 우선 현재 주어진 값들 중에서 높은 값이 어디 있는지 확인한다. 그 고점이 나오기 전까지는 무조건 매입한다. 왜냐? 해당 고점..
-
백준 1930번: 정사면체 (Python/Java)Algorithm/Algorithm Problem 2022. 2. 7. 23:15
https://www.acmicpc.net/problem/1930 1930번: 정사면체 첫째 줄에 데이터의 개수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개의 줄에는 8개의 정수로 정사면체의 각 면의 색깔이 주어진다. 첫 수는 밑면의 색깔이고, 다음 수들은 옆면의 색이 시계방향으로 www.acmicpc.net 접근 두 정사면체가 같은지 확인하는 법을 구현하면 되는 문제. 간단하게 생각해보자. 정사면체는 이름 그대로 면이 네 개밖에 되지 않기 때문에 면 하나를 고정하고 그냥 순서대로 돌리면서 확인하면 된다. 예를 들어 각 면의 숫자가 1, 2, 3, 4라고 해보자. 여기서 1번 면을 바닥 면이라고 생각하면 나머지 나머지 면을 2, 3, 4라고 하든 3, 4, 2라고 하든 4, 2, 3이라고 하든 ..
-
백준 19952번: 인성 문제 있어?? (Python/Java)Algorithm/Algorithm Problem 2022. 2. 5. 17:17
https://www.acmicpc.net/problem/19952 19952번: 인성 문제 있어?? 인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 www.acmicpc.net 접근 전형적인 너비 우선 탐색 문제에 약간의 구현을 더한 문제다. 때문에 너비 우선 탐색 부분은 기본 개념을 찾아보는 걸로 하고, '약간의 구현' 부분을 살펴보도록 하자. 일반적으로 너비 우선 탐색을 할 경우, 시작 점에서 도착 점까지의 거리를 물어보는 경우가 많다. 그런데 여기서 물어보는 것은 내 남은 체력으로 목표 위치까지 갈 수 있는지 없는 지다. 때문에 체력을 매번 체크해줘야 한다. 만..
-
백준 14442번: 벽 부수고 이동하기 2 (Python/Java)Algorithm/Algorithm Problem 2022. 2. 2. 00:39
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 접근 조건을 빼고 생각해보자면 간단한 너비 우선 탐색 문제다. 좌측 상단에서 우측 하단까지 경로를 찾아내는 것. 문제는 해당 경로까지 벽을 만났을 때 일정 횟수 부술 수 있다는 것이다. 이 부분을 구현해내는 것이 이 문제의 핵심 포인트다. 우리가 정확하게 알아야 할 것은 벽을 아예 부순 적이 없을 때, 한번 부수었을 때, 두 번 부수었을 때... N번 부수었을 ..
-
디자인 패턴(Design Pattern)이란?Computer Science/Design Pattern 2022. 2. 1. 01:25
디자인 패턴이란? 여러 사람들이 함께 개발 업무를 수행할 때, 가장 문제가 되는 것은 서로 만든 코드를 이해하는 것이다. 각자 개발 스타일도 다르고 프로젝트 규모가 커지다 보면 코드도 그만큼 길어지고 복잡해지기 때문이다. 이 모든 것은 결국 개발 업무가 지체되고 효율이 떨어지는 결과를 낳게 된다. 디자인 패턴은 이를 어느 정도 해소시켜주기 위해 나온 개념이다. 미리 정해놓은 구조 혹은 패턴을 통해 어떻게 개발을 진행할 것인가 약속을 해둔다면 위와 같은 문제가 훨씬 적게 발생하기 때문이다. 비단 위와 같은 문제뿐 아니라 유지 보수와 최적화에도 도움이 된다. 때문에 대부분의 프로젝트에서는 특정 디자인 패턴을 정해놓고 사용한다. 물론 굳이 특정 디자인 패턴을 사용하지 않아도 되는 경우에는 억지로 사용할 필요가..
-
깊이 우선 탐색 (Depth-First Search, DFS)Algorithm/Algorithm Categories 2022. 1. 30. 16:34
기본 개념 '깊이 우선 탐색'은 '너비 우선 탐색'과 마찬가지로 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나다. 루트 노드에서부터 접근할 수 있는 최대한 깊은 노드까지 탐색을 한 뒤, 전으로 돌아와 다른 노드의 끝까지 다시 탐색하는 방식을 반복해 탐색을 수행하는 알고리즘이다. 갈 수 있는 최대 깊이까지 탐색을 수행한 뒤, 다음 탐색으로 넘어간다는 알고리즘 수행 방식으로 인해 너비 우선 탐색에 보다 탐색 속도가 느리다. 하지만 특정 목표 노드가 있을 경우 해당 노드까지의 경로 혹은 도달 가능 여부를 빠르게 파악할 수 있다는 장점이 존재한다. 예시 위와 같은 총 7개의 노드를 가진 그래프를 예시로 생각해보자. 루트 노드는 A로 설정해보자. 이제 좌에서 우 순서로 깊이 우선 탐색을 진행하겠다...