알고리즘 부수기

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PNx_KACIDFAUq&categoryId=AV5PNx_KACIDFAUq&categoryType=CODE 맵의 세로 길이 H, 가로 길이 W (1 모 기업 테스트 기출과 비슷한 문제..읍읍 파도가 1번 칠 때마다 맵의 상태가 변한다. 전체를 탐색할 경우 1,000 * 1,000 * 파도횟수 만큼의 시간이 걸릴 수 있다. 즉, 상태 변화가 일어나지 않을 때까지 전체를 계속해서 탐색하며 변화시키면 풀 수 없다는 뜻 ! 최적화가 필요한 문제이다. 그렇다면, 맵 전체를 탐색하지 않고 상태를 변화시킬 수 있는 방법이 뭐가 있을까? 더이상 ..

문제링크 : https://www.acmicpc.net/problem/1431 기타의 개수 N( 시리얼 번호를 주어진 조건에 따라 정렬하여 결과를 출력 주어진 조건에 따라 정렬을 해야 하므로 가장 중요한 것은 조건이다. 위 내용이 그 조건이고 주어진 조건을 그대로 따라가면 되는 간단한 문제이다. 비교의 우선순위가 1 > 2 > 3이기 때문에 따라서 먼저 1번 조건을 확인한다. A와 B의 길이가 다를 때, 짧은 것이 먼저 온다. 즉, strlen을 사용해서 비교를 하라는 조건이다. 다음으로 길이가 같을 때 자리수의 합(숫자인 것만)을 비교한다. 이 과정은 매번 비교할 때마다 자리수의 합을 구하면 상당히 긴 시간이 걸릴 수 있는 과정이다. 그래서 문자열을 입력받으면서 입력받은 문자열..

문제링크 : https://www.acmicpc.net/problem/1309 우리의 크기 N(1N; for(int i=2;i

문제링크 : https://www.acmicpc.net/problem/11060 칸 수(1>n; for(int i=0;i

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE 상원이의 같은 반 친구 수 (2T; for(int test_case=1;test_case>N>>M; for(int i=0;i

문제링크 : https://www.acmicpc.net/problem/10164 N(세로 사이즈, 우선 경로의 수는 int 범위 안에서 수행 가능하지만 "15 * 15밖에 안되네 그냥 int로 하자"라고 생각하면 안된다. 나중에 해보면 알겠지만 입력으로 "15 15 0"이 들어올 경우가 최다 경로인데 40,116,600개가 나온다. 18 * 18이상은 int 범위가 넘어가게 된다. [ 사이즈만 보고 방심하면 히든 케이스에서 터져버린다. 다른 문제 풀 때도 주의해야할 점 ] 이제 풀이로 들어가보면 아이디어 자체는 간단하다. 중학교 때 수학에서 배운 방법을 사용하는 것이다. 이 맵에서 1번부터 8번을 거쳐 15번까지 가는 최단경로의 수는 (1번부터 8번까지 가는 최단경로의 수) * (8번부터 1..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWdXrXraFloDFAWn&categoryId=AWdXrXraFloDFAWn&categoryType=CODE A ( 원하는 이동 횟수 ) [ 1 문제가 이해가 안돼서 테스트케이스를 보고 분석을 했다. )( 는 1번만에 ()라는 올바른 문자열을 만들 수 있다. )())((는 4번만에 ()()()라는 올바른 문자열을 만들 수 있다. 문제 설명에서 문자열 T가 올바른 문자열이면 ( T ) 도 올바른 문자열이다. 라고 되어있지만 1) )))(((을 ()()()로 만드는 데는 3+2+1 = 6 번이 필요하다. 2) )))(((을 ((()))로..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWgqsAlKr9sDFAW0 정수 N (1 D5라서 겁먹고 시작했는데 단순한 문제였다. 문제가 어렵다기 보다는 테스트 케이스가 10,000개에 수의 범위가 10^12기 때문에 어떤 방법으로 시간을 줄여서 풀 것인지가 중요한 문제이다. 따로 줄이는 과정을 생각해보지도 않았고 while문 돌렸는데 풀려서.. 다른 사람들이 어떤 방법으로 시도를 했고 시간초과로 고민을 하는지는 잘 모르겠다. -------------------------------------------------------------------------------------..