정신 차리고 살자

문제 (https://www.acmicpc.net/problem/1990) 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 소수&팰린드롬을 푼 직후에 풀어서 처음엔 쉽다고 생각했는데.. 계속 시간 초과가 발생했다. 1부터 1억까지의 숫자들 중 소수이면서 팰린드롬인 숫자를 모두 출력해보았더니 최댓값이 10,000,000을 넘지 않았다! (캡처를 못해두었는데 대략 9천7백만 정도?) 따라서 반복문의 최댓값을 10,000,000으로 설정하고 숫자의 범위가 b를 넘어가면 반복문을 탈출했다. [소스코드] ..

문제 (https://www.acmicpc.net/problem/1747) 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 문제이다. N부터 반복문을 돌며 소수와 팰린드롬을 둘 다 만족하는지 확인한다. 만족하는 숫자를 발견하면 바로 반복문을 탈출한다. 이 문제에서 했던 실수,, 처음엔 N의 최댓값이 1,000,000인걸 정답의 최댓값이 1,000,000인 줄 알고 for문의 두 번째 인자를 i

문제 (https://www.acmicpc.net/problem/1043) 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온파인드로 해결한 문제이다. 1. 각 파티에 오는 사람들끼리 연결시킨다. (unionParent) 2. 전체 파티의 인원수만큼 반복문을 돌며 처음 입력받았던 진실을 아는 사람과 연결되었는지 확인한다. (findParent) 2-1. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재한다면? 그 파티에서는 거짓말을 할 수 없으므로 반복문 탈출 2-2. 해당 파티에 진실을 아는 사람과 연결된 사람이..

문제 (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 값의..