어흥

문제 링크: www.acmicpc.net/problem/1821 1821번: 수들의 합 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있 www.acmicpc.net 1. 주의할 점 - 파스칼의 삼각형을 통해 공식을 유추할 수 있어야 한다 2. 구현 - 수가 N이면, n-1C0부터 n-1Cn-1까지 총 N개의 수가 나온다. 해당 수들이 위에 배치될 숫자가 나타난 횟수다 - 조합 값을 저장해놓기 위해 Factorial[] 배열을 통해 0!~9!사이의 수를 저장한다 - setMul() 함수를 통해 n-1C0~n-1Cn-1값에 해당하는 값을 Mul[] 배열..

문제 링크: www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 주의할 점 - 두 포인터 or DP를 이용하여 해결한다 2. 구현 - 모든 수가 3만 이하의 자연수다 → i~j까지의 합이 Target번호라면, j이후의 Arr[] 배열의 원소를 더할 필요가 없다(더하면 초과하므로) 2-1) 두 포인터 - L,R를 모두 인덱스 번호 0부터 시작한다. Sum을 통해 L과 R 사이에 존재하는 모든 원소의 합을 저장한다 - ..

문제 링크: www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1. 주의할 점 - 계산 과정에서 int의 범위를 벗어날 수도 있다 2. 구현 - 서로 다른 자연수 N개 + N이 최대가 되도록 → 1+2+3+...N-1+N가 최대 N개. 즉, N*(N+1)/2 > num; result = sqrt(2*num); while(result){ if((long long)result*(result+1)

문제 링크: www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 1. 주의할 점 - 오토마타 혹은 정규표현식에 대해 알고 있으면 편하다 2. 구현 - 정규표현식의 패턴을 설정한다 - 입력받은 문자열이 정규표현식의 패턴을 만족한다면 잠수함을, 아니라면 잡음을 출력한다 [C++] #include #include #include using namespace std; int main() { string str; cin>>str; string ptn = "(100+1+|..

문제 링크: www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 1. 주의할 점 - Automata 혹은 정규표현식 사용법에 대해 알고 있어야 한다 2. 구현 - 위에서 언급한 조건을 정규표현식으로 나타낸다. 단, 이때 (100+1+|01)+가 아닌 [100+1+|01]+로 할 경우, 오답이 발생한다([]의 경우, 1개만 만족해도 True를 반환하기 때문) - matches() 함수를 사용하여 패턴과 일치하는지 Boolean값으로 Return받고 삼항..

문제 링크: www.hackerrank.com/challenges/alternating-characters/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings Alternating Characters | HackerRank Calculate the minimum number of deletions required to convert a string into a string in which consecutive characters are different. www.hackerrank.com 1. 주의할 점 - 재귀형식으로 풀지 말것(최대 10^5번 → StackOverFlow 발생) ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 1. 주의할 점 - 지문을 정확히 읽어야 한다 (만일 경로가 여러개일 경우, 알파벳 순서가 앞선것 출력) - 알파벳 순서에 대한 처리를 수행한다 2. 구현 - 티켓에 포함된 공항명을 Map에 담는다. 또한, 경로에 대한 정보를 V[출발공항 번호]에 '도착공항'을 담는다 - V[] 벡터에 대해 알파벳 숫자가 앞선 순서대로 정렬한다 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 1. 주의할 점 - TLE가 날까..? 하는 방식으로 풀어도 TLE가 발생하지 않는다 2. 구현 - 2^20 은 대략 10^6으로 1초인 10^9보다 작으니 브루트포스로 풀어도 가능하다 - 각 수를 총합에서 더하거나 빼면서 진행한다. 끝까지 다다른 경우, Target과 숫자가 일치하면 1을, 아니라면 0을 반환..