알고리즘 부수기

문제 링크 : https://codeforces.com/contest/1080/problem/C 사실 문제는 많이 어렵지 않았다. 결과 개수만 long long으로 하고 좌표를 long long으로 선언하지 않아서 계속 맞왜틀을 시전한 문제. 문제에 대한 자세한 내용은 링크를 통해 확인하기로 하고 해결한 방법은 다음과 같다. 우선, black과 white의 개수가 있다. 이 때, white의 개수는 무조건 전체 개수 - black 개수이다. 그러므로 black만 따져주도록 하자. 흰색 잉크를 쏟고 그 다음 검정색 잉크를 쏟는 순서이다. - 먼저 원래 black이었던 칸의 개수를 구해준다.( 1,1이 w이므로 무조건 전체 칸 개수 / 2 ) - 다음은 흰색을 쏟은 상황이다. 흰색에 흰색을 쏟은 경우는 개수..

https://codeforces.com/ Codeforces에는 각 유저마다 Rating이 존재한다. 그리고 이 Rating은 Codeforces에서 시행하는 Round들을 통해 올릴 수 있다. 매번 메일이 오는데 전부 무시하다가 처음으로 참여를 해봤다. 참여한 라운드는 Codeforces Round #524 (Div.2) 문제수는 총 6문제였고 뒤로 갈수록 난이도도 올라가고 점수도 많이 주는 구조. 몰랐는데 Div.1은 첫 문제가 Div.2의 3번째 문제 수준이고 일정 Rating 이상만 참여할 수 있다고 한다. 그렇게 참여한 첫 Round 6문제 중에 3문제를 통과했고 뒤의 문제는 건들지도 못했다.. 다시 한번 부족함을 느낀 계기가 되었다. 제일 오른쪽의 +-숫자는 Rating의 변화를 의미하는데 ..

일반적으로 cin과 cout은 printf, scanf와 비교했을 때 속도가 현저히 느리다. 그냥 사용한다해도 이 차이로 시간초과가 발생하는 경우를 만나보지 못했고 cin과 cout이 훨씬 편하다고 느꼈기 때문에 그동안은 중요하지 않게 생각했다. 하지만 알고리즘 문제를 풀다가 이 차이 때문에 시간초과가 나는 경우를 만났다. 이 경우에 사용할 수 있는 방법이 있다. 자세한 내용은 아래 코드를 참고하자. 123ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cs ※ endl보다 \n을 사용하는 것이 더 빠름 이 3줄을 추가해주는 것 만으로 cin과 cout의 속도를 높일 수 있다 ! 일종의 편법이지만 이 방법을 사용하면 C++ 입출력 속도를 ..

문제 링크 : https://www.acmicpc.net/problem/16510 cin / cout의 입출력 속도를 높이지 않고 풀었을 때 시간초과가 났던 문제이다. 먼저 일의 개수인 N이 주어진다. 매번 일을 수행할 때 앞에서부터 수행해서 시간안에 할 수 있는 일의 개수를 물어보는 문제이기 때문에 N을 입력받으면서 누적합을 하여 값을 저장해야한다. 단순히 값을 저장할 경우 매번 앞에서부터 합하며 결과를 확인해야하기 때문이다. 다음 과제는 주어진 일의 시간이 어느 구간에 들어가는지를 확인하는 것이다. 일할 수 있는 시간이 충분히 작다면 최대크기의 배열을 생성해서 N을 받으면서 값을 늘려가는 방법으로 들어온 시간을 인덱스로 하여 확인할 수 있지만 시간, 즉 T의 범위가 2*10^9이다. 배열로 만들기에는..

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbrg9uabZsDFAWQ&categoryId=AWbrg9uabZsDFAWQ&categoryType=CODE 2048 게임을 몇 번만에 풀수 있는지 혹은 풀 수 있는지 없는지를 물어보는 문제가 아닌 단순히 주어지는 방향으로 한 번 시행했을 때의 결과를 출력하는 문제이다. 기본적인 방법은 UP의 경우 위에서부터 아래로 내려가면서, DOWN의 경우 아래에서 위로 올라가면서 확인을 한다. 우선, 방향이 문자열로 들어온다. 생각한 방법은 2가지이다. 1. 문자열 그대로 받은 후 strcmp를 통한 비교 2. up / left / right / down..

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-hF8KdBADFAVT&categoryId=AWT-hF8KdBADFAVT&categoryType=CODE 시간을 무려 5초나 준다. 그래서 처음에는 무작정 부딪혔지만 시간초과가 발생했다. 이유는 테스트 케이스가 100,000개라는 것을 못봤기 때문.. 지금까지의 문제와는 조금 다른 느낌이었다. 이 문제에서 중요한 것은 10^6개의 숫자에 대해 미리 홀수 약수합을 구해놔야 한다는 것이다. 즉, 미리 데이터를 구해놓고 test_case 루틴에 들어가야 한다는 것이다. 그 부분만 기억하면 쉽게 풀 수 있는 문제 ! 188ms가 나왔는데 89ms에..

문제 링크 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbHcWd6AFcDFAV0&categoryId=AWbHcWd6AFcDFAV0&categoryType=CODE 그래프에서 삼각형 즉, 3개의 노드가 서로간의 간선이 존재하여 싸이클을 이루는 경우를 찾는 문제다. 감사하게도 N의 최대값이 50이므로 O(N^3)이 된다고 해도 시간초과가 발생하지 않는다. ※ M의 최대값은 N(N-1)/2이므로 시간초과가 발생할 가능성이 매우 높다 ! 가장 먼저 [N][N] 크기의 배열을 먼저 생성했다. 그리고 들어오는 간선들을 a와 b 사이에 간선이 있다고 할 때 [a][b], [b][a] 배열의 값을 1로 만들어주는 ..

주문했던 종만북이 도착 ! SWTest B형, Codeforces Round 등을 진행하면서 부족함을 너무너무 많이 느껴서 귀가 닳도록 들었던 책을 구입했다. 우선, 책이 상당히 두껍다. ( 흉기 가능 ) 난이도도 꽤 높고 c++ 기반으로 정리되어 있다. 아직 제대로 안봐서 정확히는 모르겠지만 DP ( Dynamic Programming, 동적 계획법 ) 에서 포기한 분들이 상당히 많다는 책. 아래는 이 책을 선택하게 마음먹게 해준 박트리님의 알고리즘 공부 방법에 대한 글이다. http://baactree.tistory.com/52 이 책에서 가장 마음에 드는 부분이 있다. "그래프의 최단 거리 알고리즘은 크게 한 정점에서부터 모든 정점까지의 최단 거리를 구하는 단일 시작점 알고리즘과 모든 정점 쌍 간의..