본문 바로가기

백준알고리즘

[ 백준 1000 ] A+B 1. 문제 링크 https://www.acmicpc.net/problem/1000 1000번: A+B 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 첫째 줄에 A+B를 출력한다. 예제 입력 1 복사 1 2 예제 출력 1 복사 www.acmicpc.net 2. 문제 3. 문제 요약 1. 두 개의 입력 값을 받아서 덧셈 연산을 처리한다. 4. 문제 풀이 Input 2개를 받아서, 덧셈 연산을 하고, 출력한다. 프로그래밍 초보자들도 쉽게 해결 할 수 있을 정도로 설명할 것이 없는 문제다. 5. 풀이 후기 이 문제를 풀어본 이유는, 알고리즘 공부보다는 입출력에 대해서 테스트를 해보는 의미가 컸다. 그동안 .. 더보기
[ 백준 17390 ] 이건 꼭 풀어야 해! 1. 문제 링크 https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다. www.acmicpc.net 2. 문제 3. 문제 요약 비정렬 수열을 정렬하고, 범위의 합을 출력해라 4. 문제 풀이 (1) 1차원 배열의 정렬 정렬은 딱히 설명할 게 없다. 우선 문제를 풀기 위해서 임의의 순서로 들어오는 값들을 정렬할 필요가 있다. N(1≤N≤300,000)개의 데이터가 들어오는 만큼 O(N²)의 정렬법은 시간초과가 분명했기에, O(NlogN)의 복잡도를 갖는 방법으로 정렬하고자 해서, 퀵소트를 이용해서 정렬했다. (2) 배열의 부분 합 // 메모이제이션 정렬 후, 주어지는 Q(1.. 더보기
[ 백준 9095 ] 1, 2, 3 더하기 1. 문제 링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 2. 문제 3. 문제 요약 정수 N을 1, 2, 3을 이용해서 표현가능한 식의 갯수를 출력하라. 4. 문제 풀.. 더보기
[ 백준 1966 ] 프린터 큐 1. 문제 링크 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net 2. 문제 3. 문제 요약 N개의 문서가 우선순위 큐에 있을 때, M번째 문서의 출력순서를 찾는 문제이다. 4. 문제 .. 더보기
[ 백준 14648 ] 쿼리 맛보기 1. 문제 링크 https://www.acmicpc.net/problem/14648 14648번: 쿼리 맛보기 첫째 줄에 수열의 길이를 뜻하는 n(1≤n≤1,000)과 쿼리의 개수를 뜻하는 q(1≤q≤10,000)가 주어진다. 둘째 줄에 길이 n의 수열이 하나의 공백을 사이에 두고 주어진다. 수열의 각 숫자들은 모두 int형 범위 이내이다. 이후 셋째 줄 부터 q개의 줄에 걸쳐 쿼리가 주어진다. 쿼리의 형식은 “1 a b” 또는 “2 a b c d”이다. a, b, c, d는 n보다 작거나 같은 자연수이며, a≤b, c≤d임이 보장된다. www.acmicpc.net 2. 문제 3. 문제 요약 문제는 길이 N의 수열과 Q의 쿼리가 주어졌을 때, 주어진 조건을 만족하며 답을 출력하는 것이다. Type1 (1.. 더보기
[ 백준 11404 ] 플로이드 1. 문제 링크 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 2. 문제 3. 문제 요약 N개의 노드와 M개의 엣지를 가지는 Directed 그래프에서 각 점에서 다른 점들로 가는.. 더보기
[ 백준 4963 ] 섬의 개수 1. 문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 2. 문제 3. 문제 요약 주어진 2차원 배열에서, 조건을 만족하는 집합의 수를 찾는 문제이다. 상하좌우 또는 대각선으로 .. 더보기
[ 백준 1978 ] 소수 찾기 1. 문제 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2. 문제 3. 문제 요약 주어진 1000이하의 자연수들 중 소수를 찾는 문제이다. 4. 문제 풀이 소수는 1과 자기 자신을 제외한 수로 나누어지지 않는 수이다. (1) O ( N ) 주어진 숫자 X에 대하여 1< i < N 범위의 i로 나누어지면 소수가 아니다. *1은 소수가 아니지만, 식을 만족하지 못하므로 명시적으로 예외처리 (2) O( root(N) ) 여기서 성능을 개선할 요소가 조금 더 있긴한데, 사실 N 까지 모두 확인할 필요가 없다. .. 더보기

티스토리툴바