본문 바로가기

전체 글133

[백준 17144] 미세먼지 안녕!, C++ https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 본 문제는 삼성 SW 역량 테스트 기출문제로 브루트 포스를 구현하는 문제다. 문제의 조건은 다음과 같다. (r, c)에 있는 .. 2020. 2. 19.
[프로그래머스] level 3 - 섬 연결하기, C++ https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 본 문제는 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만드는 문제다. 최소비용이므로 최소 스패닝 트리를 구현하면 된다. union-find를 사용하여 kruskal algorithm을 구현하여 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#incl.. 2020. 2. 18.
[백준 1922] 네트워크 연결, C++ https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 본 문제는 최소 스패닝 트리를 구하는 문제다. 최소 스패닝 트리를 구하는 대표적인 방법으로는 prim, kruskal이 있다. 이번 문제는 kruskal을 이용하여 문제를 해결하였다. kruskal을 구현하기 위해선 우선 union-find 자료구조를 구현해야한다. 그리고 간선의 최소 비용을 먼저 연결하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36.. 2020. 2. 17.
[백준 5557] 1학년, C++ https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 본 문제는 0 ~ 20 중에서 n개를 선택하여 1 ~ (n-1) 사이에 +, -를 대입하여 계산하였을 때 결과가 n인 경우의 수를 구하는 문.. 2020. 2. 17.
[백준 1890] 점프, C++ https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 본 문제는 좌측 상단에서 우측 하단으로 이동하는데, 현재 칸에 적힌 만큼 오른쪽 또는 아래로만 이동하여 가는 방법의 수를 출력하는 문제다. 처.. 2020. 2. 17.
[백준 11058] 크리보드, C++ https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V 를 눌러 27개를 출력할 수 있다. www.acmicpc.net 본 문제는 크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대 개수를 구하는 문제로 문제의 조건은 다음과 같다. 화면에 A를 출력한다. Ctrl-A: 화면을 전체 선택한다 Ctrl-C: 전체 선택한 .. 2020. 2. 16.
[백준 15486] 퇴사 2, C++ https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 본 문제는 퇴사와 조건은 똑같다. 차이는 입력의 크기가 퇴사는 15, 퇴사 2는 1,500,000으로 퇴사 소스코드로 퇴사 2를 풀 수 없다. 퇴사할 때까지 최대로 많은 이익을 얻으려면 퇴사 전까지 많은 이득을 얻어야 하기 때문에 큰 문제를 작은 문제로 해결할 수 있다. 그리고 계산의 반복이 있다. 따라서, DP로 문제 해결이 가능하다. 이 문제는 선택 여부에 따라 .. 2020. 2. 13.
[백준 1939] 중량제한, C++ https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 본 문제는 두 개의 섬에 다리를 세워 물품을 수송하려고 한다. 그런데 각각의 다리마다 중량 제한이 있다. 중량 제한을 초과하면 다리를 통과.. 2020. 2. 11.
[백준 11725] 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 트리로 연결된 두 정점을 입력으로 들어오면 2번 노드부터 부모 노드를 출력하는 문제다. ( 단, 1을 root로 한다. ) 따라서, 모든 연결 정보를 인접 리스트에 저장하고 root부터 BFS를 이용해 탐색을 하면서 각 노드의 부모 노드를 저장한다. 2번 노드 부터 n까지 반복하면서 부모노드를 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3.. 2020. 2. 10.

티스토리툴바