Algorithm (62) 썸네일형 리스트형 [Algorithm] 백준 9184 신나는 함수 실행 c++ https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 DP 주어진 재귀함수를 DP로 구현하면 된다. a = 0 or b = 0 or c = 0 부터 a = 20 or b = 20 or c = 20까지 bottom-up 방식으로 3차원 배열을 채운다. a 20인 경우 각각 반환값을 지정한다. 그 외의 경우에는 w[a][b][c]를 반환한다. 소스코드 #include using namespace std; int w[21][21][21]; int dp(.. [Algorithm] 백준 2580 스도쿠 c++ https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 백트래킹 스도쿠를 입력받을 때 빈 칸을 vector v에 저장한다. v를 통해 빈칸의 위치를 얻고, 빈칸에 1 ~ 9 사이의 숫자를 넣어본다. 현재 넣은 숫자가 스도쿠의 규칙을 만족한다면 다음 빈칸을 채우러 간다. (백트래킹) 현재 넣은 숫자가 스도쿠의 규칙을 만족하지 않는다면 그 칸을 비워준다. (0으로 초기화) 스도쿠의 규칙을 만족하는지의 여부는 isSetNum 함수로 판단한다. 빈칸의 .. [Algorithm] 백준 9663 N-Queen c++ https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹 체스판의 행을 기준으로 i번째 행에 Queen을 놓으면, i+1번째 행으로 넘어간다. 배열 x는 인덱스는 체스판의 row(행)를 의미하고, 값은 체스판의 col(열)을 의미한다. 예를 들어, x[1] = 2가 의미하는 것은 "체스판[1][2] 자리에 Queen이 있다"는 것이다. i+1번째 행에 Queen을 놓을 자리가 없다면 i번째 행으로 다시 돌아가 다음 열부터 탐색한다. (백트래킹) 체스판[r.. [Algorithm] 백준 2108 통계학 c++ https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 최빈값이 의외로 복병이었다. 다른 것은 간단하니 최빈값 풀이만 보면, 값과 빈도수를 pair로 저장한다. 현재 입력값이 처음 나오는 값이 아니라면 해당 값의 빈도수만 + 1한다. 현재 입력값이 처음 나오는 값이라면 vector에 값과 빈도수(1)을 넣는다. 빈도수를 기준으로 내림차순 정렬한다. 정렬된 vector의 첫 번째 값이 최빈값의 된다. 만약 첫 번째 빈도수와 두 번째 값의 빈도수가 같다면 두 번째.. [Algorithm] 백준 18870 좌표 압축 c++ https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 값과 인덱스를 pair로 저장한다. 값을 기준으로 정렬한다. 현재 위치보다 왼쪽에 있는 값들의 개수(현재 값보다 작은 수 카운팅)를 해당 인덱스에 넣는다. ans에 값을 넣기 전, 이전 값과 같은 경우 분기해서 처리한다. 소스코드 #include #include #include using namespace std; vector v; int m.. [Algorithm] 자주 사용되는 입출력 루틴 1. 테스트 케이스의 개수가 입력 첫 번째 줄에 주어지는 경우 int main(){ int t, a, b; cin>>t; while(t--){ cin>>a>>b; coutb, a || b){ coutb; if(cin.eof()) break; cout 이전 1 ··· 5 6 7 8 다음
