welcome!

백준 2037 문자메세지 해설 ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ 가 각각 같은 번호를 눌러 입력해야하므로 이전에 동일한 번호를 눌렀다면 추가로 대기시간 W시간을 요구한다. 공백에 대해선 대기시간 W 이 필요하지 않다. BC, EF, HI .. 등에 대해선 여러번 눌러야하므로 P*required[알파벳]을 이용해 구할 수 있게 하였음. 입력 받는 것이 조금 까다로울 수 있다. ````C++ #include #include #include using namespace std; int a[26] = { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9 }; int required[26..

백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..

이 문제는 비교적 구현의 성격이 강한 문제이다. 해당 문제에 대해 포스팅을 남긴 이유는 삼성 B형과 성격이 비슷하기에 골랐다. 입력으로 들어온 단어들을 내 사전 (Trie) 로 저장해놓고, 4*4 배열을 규칙에 따라 순회하면서 생성된 단어를 Trie에서 탐색하는 것이 해당 문제의 풀이이다. 이 풀이 서술은 조금은 일반적인 서술로써, 구현에 대해 조금 구체적으로 이야기 해보려 한다. 1 트라이 with memory allocation 대부분이 알고있는 Trie 의 형태로써 Trie 노드가 자식 노드의 주소를 가지고 있는 것이다. 그리고 동적으로 관리하기 때문에 new, delete를 동반한다. 아래는 해당 문제에 대한 Trie 풀이 소스이다. 해당 문제 자체가 올림피아드 성격의 대회 문제이기에 구현성이 강..

삼각형의 면적을 구하는 방법 중 하나인 삼각형을 이루는 두 변(벡터)을 활용하는 것이다.참조:https://math.oregonstate.edu/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/crossprod/crossprod.html 간략히 말하면 벡터 a, b 가 이루는 삼각형의 너비는 |a| * |b| * sin (

세그먼트 트리 with Lazy PropagationIntroduction만약 문제를 풀 때 구간 질의와 관련된 문제에서 naive한 방법 또는 잘 알려진 prefix 계열의 접근으로도 풀 수 없는 것이 있다면, 한 번쯤 생각해볼 방법은 세그먼트 트리이다.세그먼트 트리는 구간에 대해 분할 해놓은 정보들을 담고 있는 트리이다. 루트노드는 [0 ... n-1] 구간에 대한 특정 연산 결과가 담겨있고. 그 자식 노드는 [0 ... (n-1)/2], [(n-1)/2+1 ... n-1] 구간에 대한 특정 연산 결과가 담겨있다. 이는 초기화 단계 init 에서 수행된다.이러한 트리는 분할정복을 따르며, 재귀적으로 파고 들어가 자식노드의 결과값을 부모노드가 받고 또 그 결과를 재사용하기 때문에 납득할 만한 초기화 수..

문제보기https://www.acmicpc.net/problem/1081 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다. 풀이이 문제는 철저하게 수학 문제이다. 나는 접근방법을 보고나서야 풀 수 있었다. 접근법은 10단위로 생각할 것.10 ~ 29 까지 1 단위 자리의 0~ 9 의 발견횟수는 각각 (2-1+1) 이다. 이를 기준으로 계산한다.만약 Lower, Upper 구간이 0이 아니라고 해보자. 이 경우 0 으로 맞춰줘야한다. - Lower, Upper 도 1씩 올리던,- Lower, Upper 를 1씩 내리던,- ..

문제보러가기https://www.acmicpc.net/problem/6549 히스토그램에서 가장 큰 직사각형 흥미로운 문제다 생각의 진행은 다음과 같다.Main Think.[l ,r] 특정 구간내의 가장 큰 직사각형은 무엇인가? 김 : 가장 높이가 낮은 것을 기준으로 *(r-l+1) 가로길이 를 하면된다. 정 : 그렇겐 할 수 없다. 그렇게 푼다면 O(n)의 솔루션이 가능하다. 반례는 쉽게 구할 수 있다. 가로 길이가 2인 것을 직사각형 set을 생각하고 h 배열이 다음과 같다고 해봐라 [1, 1,000,000] 가장 큰 직사각형은 2인가? 1,000,000 인가? 김 : 내 솔루션이 틀렸다는걸 이해했다. 그러면 다음과 같이 해보자. 이건 조합문제라고 생각한다. 어쨌든 모든걸 시도하지 않으면 정답을 찾을..

문제보러가기https://www.acmicpc.net/problem/15483 문제 정의문자열 A와 B가 있다.A를 어떠한 동작을 통해 B와 같게 만들려고 한다. 이 때 최소한의 동작 횟수를 구하시오. 각 순간마다 세가지의 선택을 할 수 있다.- 1 삽입- 2 삭제- 3 교체 이 문제를 어떻게 해결할 수 있을까? 이 문제의 접근법은 모든 가능성을 탐색하는 것이다.재귀를 이용하여 두 문자열의 다름 정도의 비교를 할 수 있다. String S1 의 i 인덱스, S2 의 j 인덱스를 다름을 비교하여, 만약 같다면 다음 비교 스테이지인 S1의 i+1, S2의 j+1로 넘어간다. 만약 다르다면, S1에게 3가지 동작을 수행할 수 있다.삭제, 더하기, 교체 이다.만약 삭제하는 경우 다음 비교 스테이지인 S1의 i+..

Codeforces 1092C Prefixes and Suffixes문제 보러 가기https://codeforces.com/contest/1092/problem/C 문제 설명문자열 길이 정수 n 을 입력받는다. 그리고 2*n-2 개의 문자열을 입력받는다. 이때 문자열들은 다음을 만족한다.1 입력받는 문자열은 길이가 (1 ~ n-1)인 문자열이 각각 두개씩 있다.2 각각 문자열들은 n 길이의 문자열 S의 접두어거나 접미어이다. 이때 각각의 문자열이 S(접미어), P(접두어)인지 2*n -2 길이로 문자열 정보를 출력하라. 예제입력5baaababaabababaababa 출력SPPSPSPS 입력3aaaaaa출력PPSS 입력2ac출력PS 문제에 대해 이야기해본다. 내가 느끼기엔, 이 문제는 Div 3 Conte..

codeforces 1060C Maximum Subrectangle 문제보러가기https://codeforces.com/contest/1060/problem/C 문제 정의각각의 길이 n, m 인 1차원 배열 a, b를 서로 곱해서 2차원 배열을 만든다.행렬곱의 결과 c(i,j) = a(i) * b(j) 이다. 이때 c에서 가장 큰 사각형의 넓이를 구하시오. 단, c(i,j)의 합이 수 k 를 넘지 않아야한다.a와 b의 길이는 각 각 최대 2,000 사이즈이다. 1