목록Algorithm (428)
Mini

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 의사코드 1. dp[i]를 정의하고 2. 채워나가면서 규칙(점화식)을 발견하라. 2. 전체코드 #include using namespace std; int n,a[1004],dp[1004]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); c..
https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 관찰, 규칙성발견 1. 완탐 -> 너무 빡구현 & 10^15 -> 불가능 2. 관찰을 통한 규칙성발견 1(1) 2(10) 2(10) 3(11) 3(11) 5(101) 4(100) 5(101) 5(101) 6(110) 6(110) 7(111) 에서 최초0을찾고 // num and i ==false -> 최초0의 위치 그곳을 1로바꾸고 // *or1 -> 무조건 1이됨 이전비트를 0으로 바꾸면 ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. top-down dp 위에서부터구하는 dp를말한다. 재귀로 구현한다. fibo(15)=fibo(14)+fibo(13) ... 2. bottom-up dp 위에서부터구하는 dp를말한다. 반복문으로 구현한다. fibo(3)=fibo(1)+fibo(2) / fibo(4)= ... / fibo(15)= ... 3. 상하좌우탐색 문제점 -> or 아래 or 5시대각선 탐색은 배열을 i,j 한칸씩 탐색하면서..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 의사코드 1. dp도 배열한칸씩 탐색하는것이다. 2. pass 조건을 잘 생각하면 된다. 3. dp[i][j]= 어쩌구 가 아닌 // d[next] +=d[cur] 형태로도 짤수가 있다. 2.전체코드 #include using namespace std; typedef long long ll; ll dp[104][104],a[104][104]; //오큰수의 갯수 [길이][시작숫자] ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 의사코드 1. 규칙발견 && 테이블정의 : dp [길이][끝나는숫자] 의 갯수 아래숫자 == 위행의 좌측 + 위행의 우측 이다. 2. 주의사항 %1억할때, (a%1억 + b%1억) %1억해야 올바른 값이 나온다.. 2. 전체코드 #include using namespace std; typedef long long ll; ll d[104][12]; //오큰수의 갯수 [길이][시작숫자] ll n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1. 의사코드 1. 아래칸 = 위칸의 총합인것을 발견할수 있다. 2. 전체코드 #include using namespace std; typedef long long ll; int d[1004][10]; //오큰수의 갯수 [길이][시작숫자] int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; fi..
https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 우선순위큐 의사코드 1. 문제점 : 큐2개를두면, 실제 최대힙에서는 삭제되어도 최소힙에서는 삭제가 안되므로 제대로 비었는지 확인이 안된다 -> 해결 : cnt 변수 정의 //현재 큐에 있는원소의 갯수 2. 시키는대로 연산 구현후, cnt==0이면 실제로 pq1, pq2의 원소를 다 뺴주어야한다! (tc1번 걸림) 2. 우선순위큐 전체코드 #include using namespace std; ..
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 1. 의사코드 1. a+b의 결과를 답은 배열v1생성 2. c+d의 결과를 담은 배열 v2생성 3. v2에서 -v1을 이분탐색후 UB-LB == 해당순서쌍의갯수를 ret에 더해나감 2.시행착오 위의 3번과정에서 단순히 binary_search가 참이면 ret+1을 함 문제 : v1 : 2 , v2 : -2 -2 -2 일때, 순서쌍은(0,0,2,2) (0,0,2,3) (0,0,2,..