컴퓨터 프로그래밍(암호학, 알고리즘)

1. 에디터 (백준 1406) 2. 조세퍼스 문제(백준 1158) ---------------- 1. 에디터(백준 1406) 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 ..

1. 후위 표기식(백준 1918) 2. 오아시스 재결합(백준 3015) 3. 문자열 폭발(백준 9935, 10750) ---------------- 1. 후위 표기식(백준 1918) 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오 입력 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어..

1. 행렬곱 순서 2. prime - 최대공약수가 1인 수열 개수 3. 가장 긴 증가하는 부분 수열 4. 교차하지 않는 원의 현들의 최대집합 (백준 2673) 5. 식당 (백준 6101) 6. 김치배달(백준2184) 7. 1,2,3 더하기 (백준 9095) 8. 동전 바꿔주기 (백준 2624) 9. 내리막 길 (백준 1520) ------------------------------- 1. 행렬곱 순..

1. 막대기 2. 합분해 3. 폐지줍기 4. 동전2 5. 돌다리 건너기 6. 바둑돌 잇기 ---------------------------- 1. 막대기 n가지 종류의 막대기가 있다. 막대기의 길이는 모두 다르다. 이 막대기들을 적당히 사용해서, 총 길이가 K가 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 막대기는 여러번 사..

1. 피보나치 - 단순 1차 2. 파스칼의 삼각형 -단순 1차 3. 배낭 - 4. 이친수 -이진 DP 5. 인접한 비트의 수 -이진 DP 6. 롤러코스트 - 3차원 7. 집합 -2차원 ----------------------- 1. 피보나치 수열 아래와 같은 규칙성을 갖는 수열이 있을 때(피보나치 수열), 임의로 주어지는 n번째 수열 값을 구하시오. (..

1. 접미사 배열 2. KMP ---------------------------- 1. 접미사 배열 - 한 문자열에서, 나올 수 있는 모든 가능성 있는 접미사를 사전순으로 정렬해 놓은 배열 - 큰 문장이 있을 때 '찾기' 기능 구현에 적합. <- 찾으려는 문자열은, 항상 접미사 배열의 접두사 - 접미사배열을 만드는 데는, 일반적인 ..

1. 스택 2. 큐 3. 덱(Deque) 4. 링크드 리스트 5. 상호배타적 집합(disjoint set) 6. 세그먼트 트리 -------------------------------- 1. 스택 - FILO (First In Last Out). - stl의 stack 클래스 사용하면 간단 사용 가능. push, top, pop, empty, size - 알고리즘 문제풀이에 사용되는 스택은, 배열로 쉽게 구현해도 됨 (사용될 최대 크기가 결정되어 있기에) int st[1001],top=0; st[++top] = 1; //push(1) int a = st[top]; //top() top--; //pop st[top--]; //top() and pop() if(top==0) //empty 2. 큐 - FI..

1. 1x2 2x1 타일 (백준 11726) 2. 1x2 2x1 2x2 타일 (백준 11727) 3. 1x2 2x1 2x2 타일 응용 (백준 1720, 1793) 4. 3XN 타일 (백준 2133) 5. 4XN 타일 (백준 2718) --------------- 1. 1x2 2x1 타일 (백준 11726) 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기..

다이나믹 문제를 유형별로 분류해 보면, 1. 단순 1차원 1.1로 만들기(백준 1463) 1.2 피보나치 수열 1.3 파스칼의 삼각형 2. 2차원 2.1 LCS(Lognest Common Subsequence) 2.2 집합(최소차) 3. 냅섹류 2차원 3.1 배낭 4. 3차원 4.1 롤러코스트(소가 만드는) 5. 이진분류 5.1 피보나치의 0, 1 리턴 횟수 (백준 1003번 문..

필수로 알아야할 내용 1. 사선 정리 : 다각형 면적, 각도 방향성(CCW,CW,직선) 판별 --> 외적과 동일 2. 내적(직각여부, 투영), 외적(면적, 각도방향성) 3. 점과 직선 사잇거리 4. 라인 교차 5. 내/외부 판별 6. convex hull --------------- 1. 사선 정리 세 점 P(x1,y1), A(x2,y2), B(x3,y3)가 있을 때, 삼각형 APB의..