백준

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. Logic - 집중국의 수신 가능 영역을 최소화 시키기 위해서는 집중국을 세울수 있는 갯수로 지어진 k만큼 다 세워 줘야 한다. 센서를 세우는데 가장 적합한 위치는 오름차순 정렬을 했을 때 인접한 두 센서의 가운데에 세워야 한다. 케이스에서 나온 1 6 9 3 6 7 > 오름차순 정렬 1 3 6 6 7 9 > 인접한 두 노드의 거리를 빼주기 dist : 2 3 0 1..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..

1. 개요신입 개발자로 취업하기 위해서는 코딩테스트는 거의 필수인 듯하다. 처음 시작할 때 백준 티어 기준 브론즈 5에서 현재 골드 1까지 올라오고 나서 회고 겸 처음 시작할 때 뭐부터 어떻게 해야 할지 정말 모르겠는 알고리즘 공부에 대해서 정리해 볼 것이다. 이 글은 지극히 주관적인 기준이며 알고리즘 및 코테 공부를 하는데 하나의 작은 기준?으로만 생각하고 각자 자신에게 맞는 공부법을 찾길 바란다.2. 알고리즘 공부 방법1. 약 30분 ~ 1시간 정도 시간을 정해놓고 그 시간을 넘겨도 못 풀면 구글링으로 다른 사람이 푼 코드를 보고 공부한다. 2. 풀이를 보고 복붙 하지 말고 이해하고 찾아보며 직접 따라 쳐본다. 백문이 불여일타 > 그냥 복붙 하면 살 뺀다고 하고 운동 유튜브 보고 운동했다고 하는 거랑..

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) ..