https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ 0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다. 이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다. 1. 최소 힙의 값들은 모두 최대 힙보다 커야한다. 2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다. 3. 최..
https://www.acmicpc.net/problem/19948 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net 이 문제.. 약 10번의 시도 끝에 겨우 풀었다. C++를 이용한 답안 코드가 없길래 혹시 누군가 필요할까 싶어 글을 적게 되었다. 우선 문제를 꼼꼼히 읽자..! 자신과 똑같은 것이 다음에 오면 2번이 아니라 1번으로 친다는 것을 읽지못하고 좀 오래 헤매었다. 그리고, 주어진 키보드로 제목까지 입력할 수 있어야한다. 문제 풀이 우선 입력들을 다 받자 제목이 되는 문자들을 다 저장한다. 원하..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제분석 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력..
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 내가 푼 코드 #include #include #include using namespace std; int n, k, b; int cnt,num; bool arr[100001]; bool cmp[100001]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> b; for (int i = 0; i > num; //arr[i..
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제풀이 dfs문제이다. 알맞은 조합을 고르는 법은 다음과 같다. 1 2 3 3 1 2 위 테이블에서 처음 인덱스 1 -> arr[1]은 3 -> 인덱스 3 -> arr[3]은 2 -> 인덱스 2 -> arr[2]는 1 순서로 탐색을 진행한다. 만약 이 때, 처음 인덱스로 돌아온다면 조건을 만족시키도록 수를 뽑을 수 있는 경우인 것이다! 이 경우에는 pivot만을 저장해주고, i를 1..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제분석 누구나 쉽게 알 수 있는 오목게임이다. 구사과와 큐브러버는 10x10크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는데, 바둑판의 상태가 입력으로 주어지고 구사과가 턴을 한 번 더 가졌을 때, 즉, 한 수를 두었을 때 이길 수 있는지 구하는 프로그램을 작성해아한다. 오목의 승리 룰은 가로,세로 대각선 방향 중 하나에서 자신의 돌이 5개 이상 연속하는 것이다...
