전체 글138 [백준 2573] 빙산, C++ https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 본 문제는 2006 한국정보올림피아드 초등부 2번 문제다. 지구 온난화로 인하여 북극의 빙산이 녹는다. 바닷물은 0, 빙산은 10이하의 자연.. 2020. 2. 25. [백준 10868] 최솟값, C++ https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 www.acmicpc.net 본 문제는 구간의 최솟값을 구하는 문제다. 근데 입력이 100,000이다 그래서 O(n^2)으로 풀 수 없다. 입력이 큰데 구간의 최솟.. 2020. 2. 21. [백준 11404] 플로이드, C++ https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 본 문제는 제목을 통해 알 수 있다. 바로 플로이드 와샬 알고리즘을 이용해서 푸는 문제다. 플로이드 와샬 알고리즘은 간단하다. 1 2.. 2020. 2. 21. [백준 1916] 최소비용 구하기, C++ https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 본 문제는 다익스트라를 이용하여 풀 수 있다. 다익스트라 알고리즘의 설명은 링크를 참고하길 바란다. 다익스트라 알고리즘에서 시간을.. 2020. 2. 21. [백준 14891] 톱니바퀴, C++ https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 소스 코드 추가+) // 쓸때없이 어렵게 코딩해서 쉽게 다시 코딩하였습니다. // 아마도 이전 소스코드는 비트마스크 뽕에 차있었을 때.. 2020. 2. 20. [백준 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 16 다음
