공부하자

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 결과적으로 set을 사용하면 아주 쉽게 풀수있었던 문제인데, vector, 그것도 pair형 vector를 선언하고 탐색 및 삭제를 알아보다가 시간초과가 났고, 계속 구글링을 하며 돌파구를 찾아보다가 시간을 많이 버린 문제이다. 반복문 안에서 O(N)짜리 erase와 remove를 때리고 있으니 시간초과가 안나는것이 이상하지. 처음부터 set으로 가닥을 잡고..

https://www.acmicpc.net/problem/2903 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 결과값의 규칙성을 찾아 일반항을 구하고 재귀함수를 이용하여 풀면 금방 풀린다. 하지만, math 헤더의 pow를 바로 출력하려다가 지수표기법으로 출력되면 틀렸다고 판정되니, 이 부분만 주의하여 풀면 될 듯 하다. #include #include using namespace std; int arr[16]; long long int f(int a) { if (a==1) return 3; el..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 백준 단계별 풀어보기 정렬 탭에서 가장 티어가 높았던 문제였다. 높다해도 실버2 정도기에 vector 정렬을 이용한다면 간단히 풀 수 있었다. 하지만 이 문제의 관건은, 주어지는 N의 범위가 최대 1,000,000이므로, 최대한 O(N^2)를 이용하지 않고 풀어내는 것이다. 필자 또한 처음에 기본 반복문 안에 vector를 find하는 함수를 넣..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 실버5로 어려운 문제는 아니지만 아주 오랜만에 백준을 풀면서 기록해둘것이 좀 많아 쓰게 되었다. 풀이 풀이방식은 간단하다. int와 string을 쓰는 pair형 vector에 단어 길이와 단어를 입력받고 정렬한 뒤, 중복제거를 해주고 출력해주면 끝이다. 구현 #include #include #include using namespace std; int main(void) { int N;..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 간단한 그리디 알고리즘 문제로, 조금만 다르게 생각해본다면 쉽게 풀 수 있는 문제다. 풀이 가장 단순하게 브루트포스를 이용하여 모든 인덱스를 전수조사하는 방법도 있겠지만, 그렇게 될 경우 반복문 2개를 사용하게 되어 연산 횟수가 10B 가 된다. 따라서, 반복문 하나만으로 해결해야 하는 문제이다. 다음 특성만 생각하면 무척 쉬운 문제이다. 1. 지원자 중, 두 심사의 등수 모..

16953번: A → B (acmicpc.net) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 백준 #12904 A와 B와 상당히 유사한 문제이다. 다른점이라고 한다면, data-type이 string이 아닌 int 라는 점..? 알고리즘 분류는 그래프와 BFS로 되어있던데, 굳이 BFS를 활용하지 않아도 충분히 풀 수 있다. 풀이 B에서 A를 만드는 알고리즘으로 바꾸어 생각해보자. 그렇다면 적용할 수 있는 연산은 B에 따라 총 3가지로 정해지게 된다. case 1. B의 마지막 숫자가 1인 경우 : 10으로 나누어 줌 (마지막 숫자인 1을 없애주는 효과) case 2. B가 짝수인 경우 : 2로 나누어 줌 case 3. B의 마지..

12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 아무리 생각해도 브루트포스로 풀면 시간초과가 나올거 같아 생각을 하던 중, S에서 T를 만들지 말고 T에서 S를 만드는 방법으로 생각하니 금방 풀렸다. 풀이 T에서 S로 만드는 알고리즘으로 바꾸어 생각해보자. 그렇다면 적용할 수 있는 연산은 T의 마지막 글자에 따라 무조건 하나로 정해지게 된다. case 1. T의 마지막 글자가 A인 경우 : pop_back() case 2. T..

1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 저번 학기 자료구조 수업때 배웠던 중위표기식 -> 후위표기식 변환 알고리즘을 복습할겸 다시 풀어보았다. 자료구조 수업때는 JAVA 환경에서 직접 stack 함수를 만들어 구현하였는데, 이번에는 C++환경에서 stack 라이브러리를 가져와 새로 구현하게 되었다. 오랜만에 구현하는 내용이라 그런지, stack에 담긴 연산자 우선순위를 고려하여 처리해주는 부분에서 조금 버벅거렸다. 구현 #include #in..

17609번: 회문 (acmicpc.net) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net #1254에서 다뤘던 팰린드롬 관련 문제이기도 했고, 애초에 그리 어려운 문제는 아니었지만, 중간에 반례를 찾던중 접근 방식을 한번 갈아 엎어서 시간이 오래 걸렸다. 팰린드롬 (palindrome) / 회문 (回文) 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. #1254 팰린드롬 만들기와 같은 내용을 담고있어서 접근하기엔 수월했다. 처음엔 #1254에서의 코드를 조금 고쳐 함수 하나로 처리하도록 만들었다. 기존 C++ 코드 (함..

1254번: 팰린드롬 만들기 (acmicpc.net) 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 이해를 하고나면 쉬운 문제이다. 팰린드롬 (palindrome) 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. #include using namespace std; string s; int len; bool F(int a) { for (int i = 0; a+i < len-1-i; i++) { if (s[a+i] != s[len-1-i]) return false; } return true; } ..