본문 바로가기

알고리즘/백준

 (49)
9095 - 1,2,3 더하기[S3] 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 DP 예제의 문제. 1, 2, 3을 만들 수 있는 경우의 수를 구한다. 4 이상의 수부터는 이전 값(1, 2, 3) .. (N의 경우라면 n-1, n-2, n-3)의 모든 경우의 수를 합하면 된다..
2805 나무자르기(S2) 문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱..
9012 - 괄호[S4] 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은..
1260 - DFS와 BFS[S2] 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ..
2606 바이러스[S3] 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 ..
1107 리모컨[G5] 문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 ..
16236 - 아기상어(G3) 문제 https://www.acmicpc.net/problem/16236 풀이 문제의 핵심은 BFS를 사용하여 가장 가까운 먹이를 찾고 이를 반복하는 것이다. 이 부분에서 문제의 조건인 '먹을 수 있는 물고기가 1마리보다 많다면' 의 조건을 올바르게 구현하는데 많은 시간이 들었다. 첫 번째는 단순히 BFS의 사방 탐색 방향을 조건과 같이 위쪽 / 왼쪽 / 오른쪽 / 아래로 설정했으나, 이러한 방법이 문제가 있다는 사실을 파악하였다. 두 번째로 조건에 맞는 값들을 완전 탐색으로 전부 포집 후, 이를 소팅하려 했으나 의미없는 반복문이 너무 늘어나고 방향성을 수정하게 되었다. bfs문을 돌리면서 상어가 먹을 수 있는 조건의 먹이들을 확인하고 이를 우선순위 큐에 집어넣어 정렬한 뒤 최소값을 찾는 방법을 생각해보..
17144 - 미세먼지 안녕(G4) 문제 https://www.acmicpc.net/problem/17144 풀이 시뮬레이션 문제로, 사방탐색을 제외하면 별도의 특별한 알고리즘은 사용하지 않았다. 대개 헷갈릴 부분이 '미세먼지의 확산'을 구현하는 것이라고 생각되는데, 완전탐색으로 해당 기능을 수행하면 확산이 동시에 일어나는 것이 아니라, 이전 확산 값에 영향을 받는다. 이러한 문제를 해결하기 위해 1. 미세먼지 클래스를 생성 후, 완전탐색으로 조건에 맞는 미세먼지 객체를 생성하여 큐에 저장한다. 2. map(2차원 배열)의 값들을 전부 0으로 초기화하였다. 영향을 받게 하지 않기 위함으로, Dust Class의 내부 메서드로 확산량을 계산 후 값을 더해주는 방식으로 영향을 받지 않게 하였다. 3. 이후 자체 메서드로 구현한 바람으로 인한 ..

티스토리툴바