본문 바로가기

Coding

 (195)
1083번 소트 요즘 멘붕이 왔는지 머리가 안돌아가서 며칠 걸린 문제. 정해진 범위 내에서 최대값을 찾고 앞으로 보내면 된다. 최대값을 앞으로 보낸 뒤 cnt(문제에서는 S)가 남아있다면 남은 cnt를 이용해서 범위를 재정의하고 최대값을 찾아서 앞으로 보낸다. 이를 반복하면 끝. ex) 입력 : 7 60 10 40 30 50 20 70 1 출력 : 60 40 10 30 50 20 70 입력 : 7 60 10 40 30 50 20 70 2 출력 : 60 40 30 10 50 20 70
11650번 좌표 정렬하기 처음에 x좌표에 카운팅 소트를 사용하고 뒤의 y좌표를 머지소트를 사용하려고 했는데 카운팅 정렬은 마이너스 값을 저장할 수 없다는 것을 깨달음(멍청이). 그래서 그냥 pair를 사용해서 x,y좌표를 넣고 머지소트를 사용. x좌표 -> 머지소트 -> 값이 같으면 y좌표를 머지소트 -> 출력하고 끝 ps. 많은 분들이 c++ stl에서 제공하는 sort를 이용하심. 그 이유는 pair를 소트할 경우 first를 기준으로 정렬한 뒤 그 값이 같을 경우 second 값을 비교하여 second 또한 정렬해주기 때문이다.
1427번 소트인사이드 문자열로 받아서 나눠도 되고 숫자로 받아서 나눠도 된다. 숫자로 받아서 각 자리수를 나눈 뒤 카운팅 소트 사용.
11004번 K번째 수 그냥 정렬하고 K번째 수를 출력하면 된다. 머지소트(퀵소트를 써도 된다).
1427번 소트인사이드 카운팅 정렬쓰면 된다. 각 자리수의 숫자는 0에서 9까지 가능하므로 숫자가 나올때마다 해당 인덱스 배열에 1씩 더해주면 된다.
9372번 상근이의 여행 간단한 bfs문제. 그냥 연결되어있는 노드 갯수를 구하면 된다. ps. 근데 왜 풀면 풀수록 코드가 더러워지는 것 같지? 뭔가 마음에 안드는 코드.
1010번 다리 놓기 점화식으로 풀어도 되고 조합으로 풀어도 된다(단, 조합으로 풀 경우 크기가 크므로 조심해야된다). F[3][4]를 구해보자(발그림 죄송합니다). 맨 위 두 점을 연결하면 F[2][3]을 구하면 된다. 그 다음 점을 연결하면 F[2][2]를 구하면 된다. 이 두 경우를 더하면 F[3][4]의 값이 나온다. F[3][4] -> F[2][]+F[2][3] F[3][5] -> F[2][2]+F[2][3]+F[2][4] F[3][6] -> F[2][2]+F[2][3]+F[2][4]+F[2][5] 즉, 점화식은 F[M][N] = F[M-1][N-1] + F[M-1][N-2] + F[M-1][N-3] +.........+F[M-1][M-1] (입력 M과 N을 문제와 반대로 입력해버려서 반대인 상태로 설명) 이 점화식..
9084번 동전 N개의 동전을 이용해서 M원을 만들 수 있는 가지의 수를 구하는 문제 M=10, N=3(2 3 5)라고 예를 들어 살펴보자. 총 10원을 2원으로 채운다면 경우의 수가 몇 개 나올까? 1 2 3 4 5 6 7 8 9 10 0 1 0 1 0 1 0 1 0 1 이렇게 될 것이다. 이제 10원을 3원으로 채워보자. 1 2 3 4 5 6 7 8 9 10 0 0 1 0 0 1 0 0 1 0 10원을 5원으로 채워보자. 1 2 3 4 5 6 7 8 9 10 0 0 0 0 1 0 0 0 0 1 총액을 dp라고 했을때 dp[5]의 경우 5원을 넣는경우만 있는게 아니라 2+3원이 나올 수 있다. 즉 경우의 수 = 2 또한 dp[7]의 경우 2+2+3, 2+5 두 가지 경우가 나올 수 있다. 이를 Bottom-Up 방식으..

티스토리툴바