본문 바로가기
반응형

Programming Solve/BOJ60

BOJ 2003 - 수들의 합 2 / C++ 문제 링크 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 풀이 투 포인터 알고리즘을 사용한다. 두 포인터는 모두 인덱스 0에서 시작한다. 목표는 m을 만드는 것이므로 합이 m보다 작다면 끝 포인터(en)을 늘려나가며 sum에 더해나간다. 만약 합이 m보다 크다면 앞 포인터(st)의 수를 뺀다. 이 때, 앞 포인터가 끝 포인터보다 커진다면 그 지점에 두 포인터를 위치시키고 다시 더해나간다. 만약.. 2022. 2. 21.
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 2667 - 단지 번호 붙이기 / C++ 문제 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 지도를 입력받아 순차적으로 돌며 집이 있고 방문하지 않은 곳을 발견하면 해당 지점부터 DFS 또는 BFS를 시작하여 연결되어 있는 집을 모두 찾아 단지 수를 증가시켜주면 된다. 이러한 방식으로 모두 체크한 뒤, 단지 수와 각 단지에 속한 집의 수를 오름차순으로 출력하면 된다. 소스 코드 #include #include #include #include using namespa.. 2022. 2. 13.
반응형

티스토리툴바