https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..
분류 전체보기
코딩테스트를 처음 준비한다면 언어 기초 → 배열·문자열과 자료구조 → 완전탐색 → BFS·DFS → 이분탐색·그리디 → 동적계획법 순서로 공부해 보자. 아래는 직접 문제를 풀며 정리한 학습 방법과 단계별 연습 경로다. 기업별 출제 빈도를 집계한 순위는 아니며, 지원하는 시험의 안내와 자신의 약점에 맞춰 순서를 조절하면 된다.처음 시작할 때의 공부 순서언어와 복잡도: 입출력, 반복문, 함수, 정렬을 익히고 입력 크기로 가능한 시간복잡도를 판단한다.배열·문자열·자료구조: 인덱스와 경계값, 스택·큐·해시를 연습한다. 백준 1475 방 번호로 개수 세기를, 2346 풍선 터뜨리기로 덱 활용을 연습할 수 있다.완전탐색과 그래프: 모든 경우를 빠짐없이 만드는 방법부터 익히고 방문 배열을 사용하는 BFS·DFS로 넘..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1. Logic multiset 해설 1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다. 2. 가방의 무게를 입력받아 multiset으로 넣는다. 3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다 vector 해설 1. 보석과 가방을 벡터에 입..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1. Logic 처음 생각은 긴 문자열부터 첫번째 짜리부터 순서대로 9, 8, 7 이렇게 큰 숫자부터 넣어주면 된다고 생각했지만 문자가 중복되게 나오는 경우의 수도 있기 때문에 고려를 해주어야 한다. 예를 들어 ABC BCA 같은 경우가 대표적인데, 이때는 A와 B중 어느 알파벳에 9를 할당해 줄 지 구해야 한다. 각 자릿수에 가능한 숫자를 구해보면 A=100 B=10 C=1 > 100A 1..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. Logic 항상 작은 값 2개를 선택해서 정렬해야 최소한으로 비교할 수 있게 된다. 우선순위 큐는 우선순위가 높은 값을 기준으로 즉 값이 큰 거부터 내림차순으로 정렬해 주는 자료구조이다. 우선순위 큐를 선언과 동시에 greater인자를 붙혀주게 되면 오름차순으로 정렬되기 때문에 문제를 풀기 적절한 자료구조이다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 1. Logic - 처음 시작 1은 무조건 양수로 시작한다고 이해하고 풀었다. 왜냐면 -1 -2 +3도 있지만 테케에 포함되지 않기 때문에 n = 9일 때를 생각해 보면 처음에 12가 들어오는 경우도 생기기 때문에 1을 먼저 박고 시작하지 않고 0일때를 분할하여 계산해주었다. 부분 문제 1. cnt == 0일때(처음 시작일 때) - 1을 더할지 - 12를 더할지 2. cnt == 0이 아닐때(처음 시작이 아닐때) - 한자리만 더할지 - 한자리만 뺄지..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. Logic - 문자 하나를 지날 때 마다 체크를 해서 다음 경로에서 이전에 어떤 문자를 지나왔는지를 확인해야하기 때문에 처음에는 자료구조 중 map을 사용해서 체크했다. 경로를 체크한 후 방문 처리한 계속 남아있게 되면 다른 경로를 진입할 때 continue 처리가 되기 때문에 DFS를 빠져나오면서 map에서 키값을 false로 돌려놔준다. 방문처리 하는 법 1. 자료구조 Map을 활..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. Logic 해당 문제는 메모리 제한이 4MB로 굉장히 작으므로 배열의 수를 최대한 줄이는 데 초점을 두고 풀이해야한다. 간단한 설명은 입력받은 수를 변수에 저장한 후 입력받은 수를 기준으로 위의 수를 서로 비교하여 크고 작은 수를 가져와서 현재의 배열에 저장하는 식으로 풀이한다. 코드를 보면 더 잘 이해가 갈 것이다. 2. Code #include using namespace std; int n; int ..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 n + 1) ..
https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 1. Logic - 친구관계를 bfs를 돌면서 친구관계를 만들어준다. - Knapsack 알고리즘을 활용하여 사탕을 뺏을 수 있는 가치합의 최대값을 구해준다. 2. Code #include using namespace std; int n, m, k; vector vec[30001]; bool vis[30001];..
