** 평소 생각하던 문제 해결 전략들을 적어나갈 생각이다. 1. x좌표와 y좌표를 분리해서 생각하기x좌표만 있다고 생각하고 문제를 더 쉽게 풀어보고 이후에 y좌표를 추가하면 어떻게 풀 수 있는지 생각하는 접근 방법이다. 2. 순서를 강제하기주어진 문제가 임의의 순서를 추가 하였을 때 더 쉽게 접근할 수는 없는지 생각해보는 접근이다.보통 dp문제에서 많이 사용하는 접근 방법이다. 3. 주어진 문제를 반으로 나누기주어진 문제를 반으로 나누었을 때 왼쪽 범위에서 시작하고 오른쪽 범위에서 끝나는 답을 비교적 구하기 쉬운지 \(O(n)\)판단하여 분할정복으로 푸는 접근 방법이다. 4. 뒤에서부터 생각하기보통 앞에서 부터 결정하면 결정하기 난해한 문제들은 뒤에서부터 결정하였을 때 쉽게 풀리는 경우도 있다. 5. 일..
PS에서 사용하는 복잡도는 시간복잡도와 공간복잡도가 있다. 시간복잡도는 프로그램 수행시간을 분석하는 것이고 반복문에 크게 영향을 받는다.빅오 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행시간이 \(5n^4-7n^3+n^2+4\) 의 식을 가진다면.최고차항의 계수와 그보다 낮은 차수의 항을 제외시켜 \(O(n^4)\)와 같이 표기한다.주어진 입력의 크기가 n이라고 하였을 때 아래와 같은 코드들은 각각의 시간 복잡도를 가진다. 주어진 순서대로 위가 가장 빠르다.PS에서 보통 1억을 1초로 잡고 계산한다.예를 들어 n이 1000이라면 6번 이하로는 가능한 알고리즘이다. 공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.간단하게 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다. 보통 ..
그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..
삼성 소프트웨어 역량테스트 대비 문제 추천 14499 주사위 굴리기12100 2048(Easy)13460 째로탈출 213458 시험 감독10875 뱀2468 안전 영역1938 통나무 옮기기1600 말이 되고픈 원숭이2931 가스관1937 욕심쟁이 판다2638 치즈9376 탈옥5427 불3055 탈출1726 로봇2169 로봇 조종하기1194 달이 차오른다, 가자.2156 포도주 시식11727 2xn 타일링 211055 가장 큰 증가 부분 수열11066 파일 합치기2602 돌다리 건너기1022 소용돌이 예쁘게 출력하기3020 개똥벌레1939 중량제한3079 입국심사
주사위 굴리기 문제 지도 위에서 주어진 명령에 따라 주사위를 굴린다. 각 명령에 대해서 주사위 맨 윗면의 값을 출력하는 문제이다. 문제 풀이 시뮬레이션 문제이다. 명령이 K번 존재하므로 \(O(K)\)로 해결가능하다. 주어진 그림과 같이 항상 맨 윗면이 1 바닥과 닿아 있는 면을 6으로 생각하고 구현해보자. 오른쪽으로 구르는 경우를 예시로 들면 1. 먼저 구를수 있는지 판단(다음 좌표가 지도 내부인지) 2. 다음 주사위 상태에서 2번과 5번 면은 변하지 않는다. 오른쪽이므로, 현재 1번 면이 다음 3번 면으로 현재 4번 면이 다음 1번 면으로 현재 6번 면이 다음 4번 면으로 현재 3번 면이 다음 6번 면으로 바뀌게 된다. 3. 다음 상태공간을 만들었다면 6번 면과 지도 값을 비교하여 문제에 주어진 조건..
새로운 방 문제 (1,1)에서 (n,n)으로 최단거리로 이동하고, 만나는 방의 모든 돈을 곱해서 6진수로 변환할 때 뒤에서 부터 연속된 0의 갯수의 최대값을 구하는 문제이다. 문제 풀이 최단 거리로 이동하므로, 아래 또는 오른쪽으로만 이동 가능하다. 따라서 동적계획법을 적용할 수 있고, 결국 (n,n) 방에 도착 하고 소인수 분해 하였을 때 min(2의 개수, 3의 개수) 의 최대값을 구하는 문제로 바뀐다. 한 방에 3은 최대 6개 들어 갈수 있고 (n,n) 에서 최대 6만개 까지 존재 할수 있으므로 \(O(N^2 * 60000)\) 으로 해결 가능하다.\( dp[i][j][k]=\: i\: 행\: j\: 열에서\: 현재\: 까지\: 모은\: 3이\: k\: 개\: 일\: 때\: 최대로\: 모을\: 수있..