Scat

[BOJ] 11650번 좌표 정렬하기 - C++

"정렬"

문제 좌표 정렬하기 풀이 x,y좌표 서로 짝이 있는 좌표들을 각각 오름차순으로 정렬하는 코드이다. pair 라는 함수를 기억하면 좋을 것 같다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> #include <vector...

Posted by Yongmin on June 9, 2021

[BOJ] 11054번 가장 긴 바이토닉 부분 수열 - C++

"다이나믹 프로그래밍"

문제 가장 긴 바이토닉 부분 수열 풀이 11053번 가장 긴 증가하는 부분 수열이 왼쪽을 기준으로, 또 오른쪽을 기준으로 두 개가 진행되었다고 보면 쉽다. 즉, 11053번에서는 i번째에 해당하는 자릿수보다 자릿수, 값이 작은 수 중에서 dp값이 가장 큰 값에 +1 을 하였는데, 이를 왼쪽을 기준으로(원래처럼) 한 dp1과 오른쪽을 기준으로 한 dp...

Posted by Yongmin on June 9, 2021

[BOJ] 11053번 가장 긴 증가하는 부분 수열 - C++

"다이나믹 프로그래밍"

문제 가장 긴 증가하는 부분 수열 풀이 dp[n] : n번째 자리 수를 포함한 부분 수열 중 최장 길이이다. 그래서 dp[n] 은 1~n-1번째에 해당하는 수 중 n번째에 해당하는 수보다 작은 수에서 가장 큰 dp값 + 1이 dp[n]의 값이 될 것이다. 그렇게 n번째 자리까지의 dp값 중 가장 큰 값이 최종 정답이 된다. 예를 들어, A = {10...

Posted by Yongmin on June 8, 2021

[BOJ] 10844번 쉬운 계단 수 - C++

"다이나믹 프로그래밍"

문제 쉬운 계단 수 풀이 dp[i][j]를 i개의 자릿수를 가지는 끝자리가 j인 쉬운 계단 수라고 정의한다. 쉬운 계단 수 중 끝자리가 0인 경우는 그 다음 자릿수의 끝자리가 오직 1로만 되고 같은 식으로 끝자리가 9인 경우는 오직 8로만 된다. 예를 들어, 10과 89는 오직 다음 자릿수의 쉬운 계단 수를 101, 898로만 만들어낸다. 그 나머지...

Posted by Yongmin on June 8, 2021

[BOJ] 1463번 1로 만들기 - C++

"다이나믹 프로그래밍"

문제 1로 만들기 풀이 작은 수부터 큰 수까지 input까지 연산의 최솟값들을 저장해나갔다. 2로 나누어졌을 때의 연산자 갯수와 3로 나누어졌을 때의 연산자 갯수, 그리고 1을 뺐을 때 연산자 갯수들을 비교해가면서 최솟값들을 저장해나갔다. 2와 3으로 각각 나누어지지 않을 때는 큰 수로 대체하여 예외처리를 하였다. 소스 코드 1 2 3 4 5 6 ...

Posted by Yongmin on June 4, 2021

[BOJ] 9663번 N-Queen - C++

"백트래킹, 브루트포스"

문제 N-Queen 풀이 Reference : Here NxN 체스판 위에 N개의 퀸을 놓는 경우의 수를 구하는 문제로, 백트래킹 문제이다. Col[y] = x 는 (x, y)를 의미하며, 맨 왼쪽 열 0부터 맨 오른쪽 열 N까지 퀸을 놓고 check 함수로 동선이 겹치는 부분을 거르며 백트래킹으로 구현한 문제이다. 대각선에 위치한 동선을 거르는 ...

Posted by Yongmin on June 1, 2021

[BOJ] 15649~15652번 N과M - C++

"백트래킹"

문제 N과M(1) N과M(2) N과M(3) N과M(4) 풀이 전형적인 백트래킹 문제라고 한다. 주어진 범위가 주어지면 순열과 조합을 찾는 문제로서, 재귀함수 호출을 이용한 풀이로 진행하였다. Iteration과 재귀함수 호출을 이용해 문제를 해결하는 부분이다. N과 M이 각각 4, 2라면 맨 처음 array에 [1]이 담겨있다가, function c...

Posted by Yongmin on May 31, 2021

Format

"markdown 문법 정리"

Posted by Yongmin on May 31, 2021

[BOJ] 11650번 좌표 정렬하기 - C++

"정렬"

[BOJ] 11054번 가장 긴 바이토닉 부분 수열 - C++

"다이나믹 프로그래밍"

[BOJ] 11053번 가장 긴 증가하는 부분 수열 - C++

"다이나믹 프로그래밍"

[BOJ] 10844번 쉬운 계단 수 - C++

"다이나믹 프로그래밍"

[BOJ] 1463번 1로 만들기 - C++

"다이나믹 프로그래밍"

[BOJ] 9663번 N-Queen - C++

"백트래킹, 브루트포스"

[BOJ] 15649~15652번 N과M - C++

"백트래킹"

Format

"markdown 문법 정리"

FEATURED TAGS

ABOUT ME