본문 바로가기

분류 전체보기

[백준 1904번] 01타일 C++ 2021. 5. 12. www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 참나 다 풀어놓고 마지막에 처릴 잘 못 해서 엄청 시간쓴 문제; DP로 푸는데 cnt 함수 변수로 타일의 남은 칸을 줬음 그리고 남은 칸들은 1로 구성된 1칸 or 00으로 구성된 2칸 순으로 채워올라가면서 변수만큼의 칸을 다 채우는데 필요한 타일의 갯수를 구함 중요한건 cnt함수 내에서 메모이제이션값에 미리 %15746 처리를 했는데 변수 범위를 따지면 메모이제이션이 int 범위를 초과할 수 있고 이경우 틀림 (여..
[백준 9184번] 신나는 함수 실행 C++ 2021. 5. 12. www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 그냥 간단한 메모이제이션 문제 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std; int dp[51][51][51]; int w(int a, int b, int c) { if (a 20) { if (dp[20][20][20] != 0) return dp[20][20][20]..
[백준 1003번] 피보나치 함수 C++ 2021. 5. 12. www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 진짜 죽어도 DP로 풀고싶었다 이거 풀이보니까 뭐 0과 1이 나오는 표인가 이런거있던데 이런거말고.. 풀이법은 부분에서 나온 0과 1 이 출력된 횟수를 메모이제이션하고 각각의 부분에서 나온 횟수를 더하면 n의 0과 1이 출력된 횟수가 나온다고 짰다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include #include using namespace std; //0..
[알고스팟 LIS] Longest Increasing Sequence C++ 2021. 5. 9. algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com 난이도하인데 어려웠음... 부분 최적에 대한 부분도 조금 난해한 문제 알고리즘은 start 이후에 나오는 arr[start]보다 큰 수를 가진 부분증가수열을 찾으며 가장 큰 길이가 나오는것들을 찾는 방식 어렵다 ㅜㅜ 난이도 하 맞냐 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..
[알고스팟 TRIANGLEPATH] 삼각형 위의 최대 경로 C++ 2021. 5. 9. algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com 전체 최적해를 구하는 방식을 썼다가 최적 부분 구조를 책으로 이해하고 짠 코드 동적계획법 진짜 어려웠는데 종만북보고 차차 알아가는재미가 너무 좋다 만약 아래, 오른쪽아래 둘중 아무 값이나 현재의 값과 더했을때 큰 수를 구할 수 있다면 이를 dp를 이용해서 전체해의 최적값으로 연결지을 수 있다. 1 2 3 4 5 6 7 8 9 10 1..
[알고스팟 WILDCARD] 와일드카드 C++ 2021. 5. 7. algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 너무 어려웠다... 동적프로그래밍 진짜 어려웠던듯 풀이법은 한자리씩 대응시켜보고 *를 만나면 *까지 대응되는 문자열을 구하고 그다음부터 또 한개씩 대응시켜보는것 처음에 시간초과나서 두번째는 메모이제이션 사용했슴.. 재귀 정말 헷갈려 ㅜ 시간초과남(풀이x) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..
[알고스팟 JUMPGAME] 외발뛰기 C++ 2021. 5. 7. algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com 동적계획법이 정말 도저히 이해가 안가서 종만북 이라는 알고리즘 책을 보기 시작했다. 종만북에 나온 문제가 웹에도 있으니 종만북 공부하면서 푼 코드들을 업로드할 예정 종만북보고 내가 따로 코드를 작성하는거라 종만북 답지랑은 아마 다를것임 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..
[백준 1463번] 1로 만들기 C++ 2021. 4. 12. www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법을 공부하기 위해서 풀게된 문제. 탑다운과 바텀업 방식으로 정말 해답을 보고 따라풀며 이해하려고 노력했습니다. DP는 좀 어려운듯 ㅜㅜ 탑다운 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include using namespace std; int dp[1000001]; int f(int n) { if (n == 1) return 0; //메모이제이션 if (dp[n] != -1) return d..
[프로그래머스 LV 2] 문자열 압축 C++, js 2021. 4. 8. programmers.co.kr/learn/courses/30/lessons/60057# 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 코드가 정말 정말 정말 말도안돼서 내가 푼 코드와 다른 사람들의 풀이코드를 올릴건데.. 정말... 테스트케이스에 똑같은 글씨가 1000개 있는 코드가 없어서 맞은거지 이건 절대 맞은 코드가 아니다.. 정말 임기응변용 코드 그래서 이건 따로 알고리즘 설명같은건 안했다.....하하....... 그래도 3시간동안 머리싸매면서 한문제라도 내 손으로 푼게 정말 기분은 좋다 ...

티스토리툴바