빅맥좋아요

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 백준 11053번 가장 긴 증가하는 부분 수열을 풀어봤습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int n; int sequence[1000]; int len[1000]; void dp(int N) { for (int i = 0; i < N; ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 2156번 포도주 시식을 풀어봤습니다. base condition과 점화식만 잘 설정해주면 됩니다. 아래는 전체 코드입니다. #include #include using namespace std; int n; int wine[10000]; int cost[10000]; int dp(int n) { if (n < 0) return 0; if (cost[n] != -1) return cost[n];..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 10844번 쉬운 계단 수를 풀어봤습니다. 동적계획법 문제이고 bottom-up, top-down 두 가지 방식으로 풀 수 있습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; #define MOD 1000000000 int N; int arr[100][10]; int dp(int n, int k) { if (k 9) return 0; if (arr[n][k] != 0) return arr[n][k]; if (n == 0)..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 백준 1932번 정수 삼각형을 풀어봤습니다. 삼각형의 가로줄에서 양 끝에 있는 경우와 꼭대기에 있는 경우만 주의해서 조건을 걸어주면 됩니다. 아래는 전체 코드입니다. #include #include using namespace std; int triangle[500][500]; int cost[500][500]; int dp(int n, int k) { if (cost[n][k] != -1) return cost[n][k]; if (n == 0) { cost[0][0]..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 백준 1149번 RGB거리를 풀어봤습니다. 최적해를 구해야 하는데 매 순간 최적해를 구하는 그리디 방법이 아니라 모든 경우를 찾는 동적계획법을 사용했습니다. 마지막 집이 빨강, 초록, 파랑으로 칠해지는 3가지 경우에 대해 dp함수에 넣고, 결과값을 비교해서 최솟값을 출력하면 됩니다. dp함수에서 이미 계산했던 적이 있는 경우라면 바로 반환합니다. n==0인 상태에선 입력으로 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 백준 5430번 AC를 풀어봤습니다. 자료구조 deque를 사용해서 배열을 뒤집는 연산을 하지 않고 pop_back()과 pop_front()로 R연산을 해줬습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; deque dq; string ans[100]; bool funtion(string work, deque& dq, bool *isReverse) { for (int..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 백준 1504번 특정한 최단경로를 풀었습니다. 시작 정점에서 마지막 정점까지 v1, v2 정점을 반드시 지나야 합니다. 최단 경로의 경우의 수는 start -> v1 -> v2 -> end 와 start -> v2 -> v1 -> end 로 두가지입니다. 따라서 start정점, end정점, v1정점에 대하여 다익스트라 함수를 총 3번 사용해야합니다. 그..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 2580번 스도쿠를 풀어봤습니다. 비어있는 곳을 벡터에 넣어서 백트래킹 함수에서 사용했습니다. isPromising함수에서 같은 열, 같은 행, 같은 구역인지 체크하고 promising하면 true를 넘겨줬습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; int board[9][9]; vector v; bo..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 9663번 N-Queen문제를 풀어봤습니다. 처음엔 2차원 배열로 체스판을 만들어서 풀면 쉬울 것 같아서 2차원 배열로 풀었더니 시간 초과가 나왔습니다. 그래서 1차원 배열로 바꾸고 배열의 인덱스를 y좌표, 배열의 값을 x좌표로 가정하고 풀었습니다. board[1]=2 면 (1,2)에 퀸이 위치한 것입니다. 입력받은 n만큼 순회하면서 해당 level(y좌표)과 i(x좌표)에 퀸을 놓습니다. 그 다음 퀸을 놓..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 백준 1753번 최단 경로를 풀어봤습니다. 우선순위 큐에서 두 번째 인자에 가중치를 넣었고 가중치를 오름차순으로 정렬하기 위해 compare 구조체를 정의했습니다. 인접리스트로 풀었고 큐에 시작점과 가중치 0을 넣고 다익스트라 함수에 넣었습니다. 그 후엔 다익스트라 함수에서 시작점과 인접한 정점부터 탐색을 시작합니다. BFS와 비슷한 구조인데 가중치만 추가된 ..