목록프로그래밍/알고리즘+코딩테스트 (97)
有希
킹받는 문제. 흔히 아는 " 뿐만 아니라 \(백슬래시) 또한 n과 붙어 특수한 기능을 하므로 \도 고려해야 한다. 문자열로 넣는 방법은 "과 마찬가지로 \를 하나 붙여주면 된다. #include using namespace std; int main() { cout
원형으로 0번째 ~ 마지막 원소가 모두 제거될 때까지 무한으로 즐겨야 한다. 만약 벡터를 사용해서 원형으로 둘러 앉은 것을 구현했다고 치자, K번째 원소를 제거했다면 해당 원소는 건너뛰고 idx를 세어야 하므로 K번째 원소를 -1로 밀어버리고 스킵하는 부분을 넣어야 한다. 어쨌든 벡터는 원소 제거에 있어 비용이 n만큼 드므로 -1로 밀어야 한다. erase를 써도 무방할 테지만 웬만하면 하지 말자. 저렇게 하면 코드가 너저분해질 것이 뻔하다. 어차피 계속 순차탐색을 할 것이므로 원소 제거에 좋은 list를 사용한다. 알고리즘은 다음과 같다. 1. list에 사람을 넣는다. 2. 첫 번째 원소부터 탐색하며 K번째 사람이면 제거된 순서를 저장할 벡터에 저장하고 제거한다. 이후 cnt=1로 초기상태로 돌아간다..
우리가 찾아야 하는 점은 좌표 중 한 번씩만 등장한 녀석들을 x,y좌표로 가지고 있는 점이다. map을 두 개 써서 x, y 의 등장횟수를 저장한 뒤 1이면 출력시켜주면 된다. #include using namespace std; int main() { map posX; map posY; for(int i=0; i> x >> y; posX[x]++; posY[y]++; } auto iter = posX.begin(); while(iter != posX.end()) { if(iter->second==1) cout first second==1) cout first; iter++; } return 0; }
간단하지만 주의해야할 점이 있다. *를 찍고 나서 공백을 한 번 더 찍어주는 것이 아닌 바로 다음 줄로 이동해야 한다. #include using namespace std; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { //전체 길이 = ((2n-1) - (2*i+1))/2 for (int j = 0; j < ((2*n-1) - (i*2 + 1)) / 2; ++j) cout
문제를 읽고 입력의 끝을 어떻게 찾아야하지 고민하는 경우가 많다. 이런 문제들이 으레 그러하듯이, 무식하게 풀면 된다. 입력이 최대 100줄이고, 각 줄은 100글자를 넘지 않는다고 했으니, getline으로 100번 긁어오면 된다. 연산 시간이나 무식하게 하나하나 입력받을 때 발생할 수 있는 문맥교환등도 무시 가능할 정도로 적은 횟수이다. #include #include using namespace std; int main() { string s; for(int i=0; i
처음에는 벡터를 이용해서 0이 아니면 벡터에 넣고 0이면 개수를 센 뒤, 벡터사이즈 - 0의 개수만큼만 벡터에서 더하면 되겠지 하고 생각했었다. 문제는 가장 처음에 0 이 올 경우이다. 문제에서 주어진 3 0 4 0 케이스를 약간 비꼬아서 0 0 3 4 일 경우에 위에처럼 알고리즘을 짜게 되면 vec사이즈는 2, 0의 개수도 2가 되어 0을 출력하게 된다. 고로 stl중 stack을 이용하여 푸는게 가장 보편적이고 좋은 풀이이다. 홍대병을 버리면 되는 문제. #include #include using namespace std; int main() { stack s; int n; cin >> n; for(int i=0; i> a; if(a==0) s.pop(); else s.push(a); } int re..
주의할 점은 2,3 글자가 하나의 글자로 치환된다는 점이다. 즉, 2,3글자마자 체크하여 치환된 문자가 아니라면 따로 세야한다. 예제입력1의 예시를 보면 lj / e / s= / nj / a / k 로 나뉘는데, 현재 e에서 시작하여 문자를 체크한다고 하면 e es es= 의 3가지가 가능하다. case "e" : 2,3번째 글자를 체크해야하니 아무것도 하지 않고 case "es" : 2글자이므로 치환 문자에 속하는지 확인하고 맞다면 알파벳 개수를 1 증가시킨다. 아니라면 3글자일 수도 있으므로 아무것도 하지 않는다. case "es=" 일 때에는 3글자이므로 치환 문자에 속하는지 확인하고 맞다면 알파벳 개수를 1증가시킨다. 아니라면 치환된 문자에 속하지 않는 첫번째 글자 단독으로 하나의 알파벳이므로 알..
s배열에서 m개의 연속된 수를 더해서 d를 만들수 있는 경우의 수를 반환한다. int birthday(vector s, int d, int m) { int ret = 0; for(int i=0; i
arr이 2개 주어진다. 1번째 arr에 담겨있는 숫자들의 공배수들 중 2번째 arr의 가장 작은 값 이하인 녀석들을 num이라 한다면, 2번째 arr에 담겨있는 숫자들을 나머지가 0이 되도록 나눌 수 있는 num의 개수를 세는 문제이다. 예시를 보자면 a=[2,6]이 주어지고 b=[24,36]이 주어진다. 2와 6의 공배수는 6의 배수들이다. 6,12,18,24,30,36.... 이 중 24보다 작은 녀석들은 6,12,18,24 이다. 다시 이 녀석들 중 b의 원소들을 모두 나머지 없이 나눌 수 있는 녀석들은 6,12의 2가지고 return 값은 2가 된다. 공배수니 뭐니 수학적 얘기가 막 나와서 머리가 좀 아픈데, 수학적 얘기들을 치우면 단순한 해결법이 존재한다. a[마지막]
두 캥거루가 각자 다른 출발선에서 각자 다른 속도로 한 번씩 점프할 때 만날 수 있는가를 물어보는 문제. 속도가 빠른 녀석이 앞에 있다면 영영 만나지 못하니 NO 속도가 빠른 녀석이 뒤에 있다면 만날수도 있으므로 루프 돌면서 계산해서 만나면 YES처리해준다. 더 빠르게는, abs(x1-x2)%abs(y1-y2) == 0 라면 YES가 되겠다. while 루프를 도는 것을 한 번에 수학식으로 처리한 것이다. string kangaroo(int x1, int v1, int x2, int v2) { string ret=""; while(true) { if(v1 >= v2 && x1>x2) { ret = "NO"; break; } if(v2 >= v1 && x2 > x1) { ret = "NO"; break; ..