본문 바로가기
728x90

Algorithm36

BOJ - 2294번 동전 2 문제풀이 (DP, SET 사용) 문제 소개 n가지 종류의 동전을 갖고, k원의 금액을 최소 개수의 동전으로 만드는 어떻게 보면, 기본적인 dynamic programming 문제입니다. 하지만, 풀이하면서 몇 가지 실수가 있었어서 풀이 과정을 간단하게 정리해보려고 합니다. 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수.. 2022. 12. 28.
[코딩테스트] 카카오 모빌리티 2022 하반기 1차 코테 사용 개념 정리 이번에는 2022년 11월 26일 카카오 모빌리티 2022년도 하반기 1차 코딩테스트에서 사용했던 개념들을 정리해보려 합니다. 테스트케이스는 모두 통과시켰으나, 문제의 정답 여부는 알 수가 없어서 결과는 나와봐야 알 것 같지만 난이도 자체는 쉬웠던(?) 것 같습니다. 특히 파이썬을 사용한다면, 쉽게 해결 가능한 문제들이었던 것 같습니다. String compare C++에서 string type 변수, 즉 문자열을 비교하기 위해서는 compare method를 사용합니다. 위와 같이 compare method를 사용하면, 출력 결과는 다음과 같습니다. 이 결과로 compare method를 사용하면 두 문자열이 같은 경우에는 0을 반환합니다. 만약 두 문자열이 다르다면, 사전적인 비교를 통해 method.. 2022. 11. 26.
세그먼트 트리 (Segment Tree) 개념 정리 지난번에 문제풀이를 하면서, 세그먼트 트리를 활용할 일이 있어 오랜만에 개념을 공부했는데 기억이 잘 나지 않아서 한 번 정리해보려 합니다. 세그먼트 트리 (Segment Tree)의 정의! 우선 위키백과에서는 세그먼트 트리를 다음과 같이 정의하고 있습니다. In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. A segment tree for a set I of .. 2022. 11. 16.
백준 - 5014번, 스타트링크 문제, BFS 방식 풀이 정리 (C++) 이번에 풀이한 문제는? 백준 5014번 스타트링크 문제 풀이 정리입니다. https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net solved.ac 기준 실버 1 난이도의 문제이고 저는 BFS 방식으로 그래프를 탐색하는 알고리즘을 적용해서 풀이해 봤습니다. 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 .. 2022. 11. 9.
백준 - 11048번, 이동하기 문제 BFS및 Dynamic programming 풀이 (C++) 이번에 풀이해본 문제는 11048번 이동하기 문제로, solved.ac 기준 실버 2 난이도의 문제입니다. 요즘 들어 ps를 너무 오랫동안 방치해서 감을 살릴 겸 기본적인 예제가 없을까 하다가 적당한 난이도의 문제가 보여서 풀게 되었습니다. https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 설명부터 정리한 이후 제 풀이 과정에 대해서 정리해 보겠습니다! 문제 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나.. 2022. 10. 31.
백준 - 12100번 2048 - easy 문제 풀이 정리 이번에 풀어본 문제는 solved.ac 기준 class 5에 속하는 2048문제입니다. 다들 알고 계시는 2048게임을 5번까지 시뮬레이션했을 때 결과로 뽑아낼 수 있는 최대의 수를 찾는 문제로 원래 2048 게임은 한 번 이동이 발생할 때마다 새로운 블록이 등장하는 것과 다르게 이 문제에서는 새로운 블록이 등장하지 않는 전제 하에 시뮬레이션을 구현하면 됩니다. 문제 링크 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임은 여기서 플레이 해보실 수 있습니다! 2048 J.. 2022. 10. 13.
728x90

티스토리툴바