본문 바로가기
728x90

memoization

[백준알고리즘] 10942번: 팰린드롬? -C++ [백준알고리즘] 10942번: 팰린드롬? -C++ 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이전에 파이썬으로 풀다가 포기한 흔적이 있는 문제다. 문제를 보고 시간제한 있는 걸 보자마자 싸한 걸 느꼈다. 그래서 쉽게 구하는 것부터 생각하면서, 어떤 방법으로 문제를 풀어야 할지 고민했다. 그런데 생각보다 쉽게 풀렸다. 그래도 이전 파이썬 오답들이 정답 비율에 한몫했을 것 같다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 풀이 먼저, 팰린드롬은 앞으로 읽나 뒤로 읽나 똑같은 말이다. .. 더보기
[백준알고리즘] 1014번: 컨닝 -C++ [백준알고리즘] 1014번: 컨닝 -C++ 1014번: 컨닝 (acmicpc.net) 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 으으음.. 되게 어려웠다. 처음에는 단순히 Bruteforce 방식으로 푸는데 DFS를 적용해서 풀었다. 거의 다 풀었다가 생각해보니까 시간 복잡도가 초과한다는 것을 알게 되었다. 사실상 브루트 포스를 푸는 것이기 때문에 \(O(2^(n * m))\)의 시간 복잡도가 걸려 최대 \( 2^{100} = 1,267,650,600,228,229,401,496,703,205,376 \)라는 말도 연산.. 더보기
[백준알고리즘] 9184번: 신나는 함수 실행 -C++ [백준알고리즘] 9184번: 신나는 함수 실행 -C++ 9184번: 신나는 함수 실행 (acmicpc.net) 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 조건들이 다 주어졌기 때문에 되게 쉽게 풀었다. 문제에 적힌대로 저대로만 사용하면 시간이 오래 걸리기 때문에 하나의 장치를 두어야 한다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 추가해야 할 장치는 바로 메모이제이션(Memoization)이다. 메모이제이션은 재귀와 재귀를 사용하는 DFS, 동적 계획법과 같은 곳에서 많이 사용하는 방법으로, 이미.. 더보기
[백준알고리즘] 1946번: 신입 사원 -Python [백준알고리즘] 1946번: 신입 사원 -Python https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. www.acmicpc.net 문제 자체도 어려운 편이 아니었는데 계속 시간 초과가 나서 이상했었다. 한동안 sys.stdin.readline()대신 input()으로 다뤘더니 생긴 문제였다. 입력이 하나의 테스트케이스.. 더보기
[백준알고리즘] 11050번: 이항계수 1 -C [백준알고리즘] 11050번: 이항계수 1 -C https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수의 문지입니다. 이 문제는 범위가 짧기 때문에 이항 계수의 식을 그대로 넣어서 풀어주도록 합니다. nCk = n! / (k! * (n-k)!) 이때 저는 범위만큼 팩토리얼을 배열에 저장을 한 후 가져다가 쓰는 방식을 사용했습니다. #include int factorial_arr[11]; void factorial(void); int main(void){ int N, K; scanf("%d", &N); scanf("%.. 더보기
728x90

티스토리툴바