본문 바로가기
반응형

백준45

BOJ 2559 - 수열 / C++ 문제 링크 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 풀이 처음 생각한 방식은 포인터 2개를 이용해서 0 ~ k / 1 ~ k+1 / 2 ~ k+2 ..를 모두 더해서 최댓값을 구하려고 했다. 하지만 시간초과가 났고 포인터 2개를 더 효율적으로 쓸 수 있는 방식을 찾아보았다. 먼저 0 ~ k 를 더한 뒤 0번째 인덱스의 수를 빼고 k+1번째 인덱스의 수를 더하는 방식으로 풀면 시간초과가 나지 않는다. 소스 코드 시간 .. 2022. 2. 20.
BOJ 6438 - Reverse Text / C++ 문제 링크 : https://www.acmicpc.net/problem/6438 6438번: Reverse Text In most languages, text is written from left to right. However, there are other languages where text is read and written from right to left. As a first step towards a program that automatically translates from a left-to-right language into a right-to-left www.acmicpc.net 문제 풀이 투 포인터 알고리즘을 이용하여 0번째 인덱스와 마지막 인덱스를 차례대로 바꿔가며 문자열을 바꿔준다... 2022. 2. 20.
BOJ 1697 - 숨바꼭질 / C++ 문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 요약하면, 현재 위치 n에서 k까지 갈 때 x+1, x-1, 2*x 중 한 가지 과정을 거쳐서 갈 수 있으며 최소 시간(카운트)을 구하면 되는 문제이다. 잠시 DFS와 BFS의 개념을 살펴보면 DFS는 아래의 그림처럼 현재 branch를 최대한 깊이 탐색한 후 다음 branch를 탐색하는 방식이며 BFS는 아래의 그림처럼 인접 노드를 모두 탐색한.. 2022. 2. 12.
BOJ 1920 수 찾기 / C++, 시간 초과 방지 팁 문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 첫 번째 배열에 두 번째 배열 값들이 존재하는지 찾는 문제이다. 이진 탐색을 사용하기 위해 첫 번째 배열들은 정렬을 해준다. 두 번째 배열들은 입력받자마자 이진 탐색을 통해 해당 값들이 첫 번째 배열에 있는지 확인한다. C++에서 시간 초과를 방지하려면 (1) ios_base::sync_with_stdio(false); ci.. 2021. 9. 1.
반응형

티스토리툴바