본문 바로가기
728x90

분류 전체보기80

[c++] 계단 오르기(2579), DP 문제https://www.acmicpc.net/problem/2579 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는.. 2023. 11. 7.
[c++] 1, 2, 3 더하기(9095), DP 문제 https://www.acmicpc.net/problem/9095 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 1 복사 3 4 7 10 예제 출력 1 복사 7 44 274 풀이 DP는 점화식을 찾아야함... 2023. 11. 7.
[Pytorch] Set seed import torch import numpy as np import random import torch.backends.cudnn as cudnn def set_seed(num): torch.manual_seed(num) torch.cuda.manual_seed(num) torch.cuda.manual_seed_all(num) np.random.seed(num) cudnn.benchmark = False cudnn.deterministic = True random.seed(num) 2023. 11. 5.
[c++] 1181, 우선순위 큐 + operator 정렬 문제 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는.. 2023. 10. 25.
[c++] 2048 (Easy) (12100), 반례모음, DFS, 백트래킹, 재귀 문제https://www.acmicpc.net/problem/12100 열받아서 반례를 다 모아봤어요 반례모음 3 2 2 2 4 4 4 8 8 8 =>16 2 8 16 16 8 =>16 4 8 16 0 0 0 0 16 8 0 0 0 0 0 0 0 0 =>32 4 0 0 0 0 4 0 0 0 8 32 4 0 8 8 4 0 ->64 1 16 => 16 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 =>32 5 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 4 0 2 2 -> 32 5 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 4 2 -> 32 5 2 2 2 2 2 4 2 2 2 2 0 0 0 0 0 2 2 2 2 2 2 2 2.. 2023. 10. 10.
[c++] N과 M(1~12) 유형별 정리, 백트래킹, DFS, 재귀 중복 선택 제외시 : check 필요(사용했다는 것을 기록) 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=k //k=상태 번호 중복 선택 포함시 : check 필요 없음 중복 선택 + 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=st int st = 0; if (k != 0) st = arr[k-1]; // 비내림차순일 경우 // if (k != 0) st = arr[k-1] + 1; // 오름차순일 경우 수열 숫자들이 주어질 시에 : sort(arr, arr+N)으로 정렬 후 수행해야 한다. 수열 숫자들에서 중복된 수가 존재시 : ex) 9 5 9 7 // 정렬 후 각 상태에서 tmp로 이전 값을 저장한 후, 다음 값 선택시 비교해서 동일하면 제외하도록 해야 한다. 아래.. 2023. 10. 9.
[c++] N과 M(9) (15663), 백트래킹, 재귀, DFS 문제 https://www.acmicpc.net/problem/15663 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 4 4 2 예제 출력 1 복사 2 4 예제 입력 2 복사 4 2 9 7 9 1 예.. 2023. 10. 9.
[c++] 부분수열의 합(1182), 백트래킹, dfs, 재귀 문제 https://www.acmicpc.net/problem/1182 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 예제 입력 1 복사 5 0 -7 -3 -2 5 8 예제 출력 1 복사 1 풀이 재귀적으로 DFS 수행, 트리 한쪽의 끝까지 도달한 후 return하면서 수행한다. - check[] 배열.. 2023. 10. 8.
[STL] 순열과 조합, next_permutation #include // next_permutation 기본 형식 int a[3] = {1,2,3} do{ for(int i=0; i 2023. 10. 8.
[C++] 백준 N-Qeen (9663), 재귀, DFS, 백트래킹 문제 https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 복사 8 예제 출력 1 복사 92 풀이 이전 Queen들의 이동 방향성을 체크하는 것이 주된 키 2차 배열로 모두 체크하는 것 보다, 경향(기울기)을 파악해서 1차원으로 체크하면 O(1)로 체킹할 수 있다. 백트래킹을 이용하여 재귀적으로 DFS를 수행한다. 코드 알게 된 점 백트래킹을 통한 재귀의 과정에 대해서 .. 2023. 10. 8.
[DL] 오토인코더(Autoncoder) 본 포스팅은 DMQA 오픈 세미나 자료 및 영상을 참고하여 정리하였습니다. http://dmqm.korea.ac.kr/activity/seminar/330 고려대학교 DMQA 연구실 고려대학교 산업경영공학부 데이터마이닝 및 품질애널리틱스 연구실 dmqa.korea.ac.kr 1. 오토인코더란 무엇일까? 정의 : 레이블이 없는 비지도학습에 주로 사용되는 신경망 형태이다. 구조 : Encoder와 Decoder가 bottleneck 구조를 이룸 Encoder : 입력 데이터를 의미있게 함축된 representation한다. Decoder : Encoding 된 representation을 다시 원본 데이터로 복원 reconstruction loss : 입력 데이터와 복원 데이터의 차이를 학습하여, loss를.. 2023. 8. 23.
[c++] 백준 벽 부수고 이동하기 3(16933), bfs, 반례모음 문제 https://www.acmicpc.net/problem/16933 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 .. 2023. 8. 22.
728x90

티스토리툴바