정신 차리고 살자

문제 (https://www.acmicpc.net/problem/15927) 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분 문자열의 길이를 구하는 문제. 예제를 보면 바로 파악이 가능한데, 케이스를 3가지로 나눌 수 있다. 1. 팰린드롬 O / 문자열의 모든 문자가 같은 문자인 경우 => -1 2. 팰린드롬 O / 문자열의 모든 문자가 같지 않은 경우 => 문자열의 길이 - 1 3. 팰린드롬 X ..

문제 (https://www.acmicpc.net/problem/7490) 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 풀고 검색해보니까 대부분 백트래킹으로 풀던데 나는 백트래킹으로 풀 생각은 못했다ㅠㅠ 다음에 백트래킹으로도 풀어봐야지...! 자연수 N이 주어질 때, 연산자 개수는 N-1개이다. 각 연산자 자리에 들어갈 수 있는 것은 +, -, ' ' 총 3개이다. 중복 순열을 만들어서 각 순열이 만들어질때마다 수식을 검사한다. 공백이 있다면 이어붙이고 만들어진 수식을 계산했다. 계산된 수식의 값이 0이라면 해당 수식 문자열을 vector에 담아두었고, 아스..

문제 (https://www.acmicpc.net/problem/17070) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 가능한 이동 방법은 아래와 같다. 1. 파이프가 가로 방향일 때 - 오른쪽 방향 - 오른쪽 아래 대각선 방향 2. 파이프가 세로 방향일 때 - 아래 방향 - 오른쪽 아래 대각선 방향 3. 파이프가 대각선 방향일 때 - 오른쪽 방향 - 아래 방향 - 오른쪽 아래 대각선 방향 파이프의 오른쪽 끝 위치(x, y), 현재 파이프의 방향(가로/세로/대각선)(dir)과 함께..

문제 (https://www.acmicpc.net/problem/1477) 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분 탐색 문제이다. vector에 휴게소의 시작점과 끝점(0, l), 입력받은 위치들을 넣어주고 정렬한다. 1 ≤ 휴게소의 위치 ≤ l - 1이므로 start = 1, end = l - 1로 설정했다. 휴게소 사이의 거리인 mid를 구하고 기존 휴게소 사이에 몇 개의 휴게소를 설치할 수 있는지 계산한다. 이때, dist % mid 값이 0이라면 휴게소 위치가 겹치는 것이므로 개수를 하나 빼야 함! 예를 들어,..

문제 (https://www.acmicpc.net/problem/2776) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 10816번 (숫자 카드 2) 문제와 매우 비슷한 문제이다! 이 문제도 upper_bound, lower_bound를 사용하여 해결했다. upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 [소스코드] 더보기 2021-12-19 Silver 4 - 자료 구조 - 정렬 - 이분 탐색 - 해시를 사용한 ..

문제 (https://www.acmicpc.net/problem/2343) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 실수했던 점! - ans 초기화할 때 값은 10,000이 아닌 1,000,000,000으로 해야 함 - 블루레이의 개수가 꼭 M일 필요 없음 - cnt 초기화를 1로 해두면 편하다... 많이.... - M 모든 강의가 들어가지 않는 것이므로 mid 값이 커지도록 한다 [소스코드] 더보기 2021-12-19 Silver 1 - 이분 탐색 - 매개 변수 탐색

문제 (https://www.acmicpc.net/problem/10816) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net upper_bound()와 lower_bound를 사용하여 푼 문제! 기억하기~~~ upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 upper_bound 리턴 값 - lower_bound 리턴 값 0: value 값이 존재하지 않는 것 양수: value 값의..

문제 (https://www.acmicpc.net/problem/1654) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 전에 올린 나무 자르기와 비슷한 듯 다른 문제..! 나는 end 값을 입력받은 길이 중 가장 큰 값이 아닌 모든 길이의 합을 n으로 나눈 값으로 정했다. 각 길이를 mid로 나누었을 때 몫의 합이 n보다 - 크거나 같다면? 랜선의 길이를 더 길게 start 이동, 최댓값이라면 답으로 설정 - 작다면? 랜선의 길이를 더 짧게 end 이동 [소스코드] 더보기 20..

문제 (https://www.acmicpc.net/problem/2805) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색하는 값 (mid): 절단기의 높이 절단기의 높이가 mid일 때, 나무를 자르고 남은 길이들의 총합이 m 이상이면? - 더 큰 mid 값으로 m 이상을 구할 수도 있으므로 start를 mid + 1로 지정한다. [소스코드] 더보기 2021-05-25 Silver 3 - 이분 탐색 - 매개 변수 탐색

문제 (https://www.acmicpc.net/problem/2512) 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색하는 값 (mid): 예산 저번에 푼 1920번 문제는 배열의 인덱스를 이분 탐색으로 찾아냈다면 이 문제는 인덱스가 아니라 값들을 이분 탐색으로 찾아야 한다. 예산 요청의 총합이 m보다 크다면 이분 탐색을 진행한다. 이분 탐색을 진행할 때마다 sum을 구해야 하는데, 요청 금액이 mid 값보다 크다면 mid 값으로 더해주어야 한다. 배정된 예산들 중 최댓값인 정수를 출력해주..