알고리즘/백준

백준 1157 결과 단순한 문제인데 접근을 아스키 코드를 사용하는 방식으로해서 빙빙 돌아간것 같다. 게다가 파이썬의 함수를 익히지 못한결과 매우 1차원적인 코드를 작성했다.. 시간 차이가 5배라니.. 잘 짜여진 다른 사람의 코드를 참조하는건 필수인 것같다. c언어로 짠 것 같은 첫번째 코드 s = input() cnt = [0]*26 # A-Z까지 빈 배열 생성 # 대소문자 구분없이 알파벳 사용횟수 저장 for i in range(len(s)): if( ord(s[i])>96): index = ord(s[i])-97 cnt[index] += 1 else: index = ord(s[i])-65 cnt[index] += 1 max_index =cnt.index(max(cnt)) # 최댓값 중복 확인 for ..

알고리즘 배낭의 최대가치를 결정하는 과정은 크게 두 가지의 경우로 생각할 수 있다. 배낭의 무게보다 물건의 무게가 더 크면 물건을 넣지 않는다. 그렇지 않다면 배낭의 가치를 측정한다. (이전 물건이 있으면 전부 빼고) 새로운 물건을 넣는다. 그리고 배낭의 무게에서 새로운 물건의 무게를 뺐을 때의 배낭의 최대 가치를 고려한다. 새로운 물건을 넣지 않고 이전 배낭을 그대로 가져간다. 어떤 자료구조를 사용해야 할까? 일단, 배낭에 물건을 넣거나 빼면서 배낭의 최대가치를 결정해야 하므로 각 물건의 무게와 가치를 저장할 2차원 배열이 필요하다. i \ j 0 1 0 a의 무게 a의 가치 1 b의 무게 b의 가치 2 c의 무게 c의 가치 이를 obj[i][j]로 정의하겠다. 그리고 배낭의 무게와 물건에 따른 배낭의..

전공시간때 배웠지만 백준 11729 하노이탑 알고리즘 : 가장 마지막 과정을 생각해보면 n-1개의원반이 2번에 있고 마지막 원반을 1번에서 3번으로 옮긴 후 다시 2번에 있는 n-1개의 원반들을 3번으로 옮기는 과정이다. int hanoi(int n, int from, int mid, int to) { if (n == 1) { printf("%d %d\n", from, to); return; } hanoi (n - 1, from, to, mid); printf("%d %d\n", from, to); hanoi(n - 1, mid, from, to); } 원반 이동 횟수: 2^n-1 참고 [백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바] (tistory.com)

백준 11050 재귀함수 구현 방식에 따른 시간차이 한 단계 낮은 문제가 해결되고 이를 바탕으로 답을 얻을 수 있는 경우 재귀적 문제 해결방식을 고려해보아야 한다. 재귀함수 구현 시 주의사항 : 재귀함수를 사용하여 코드를 구현하면 스택에 함수가 쌓인 후 값이 차근차근 반환되므로 오버플로우가 발생할 수 있다. (함수호출반환에 오버플로우가 발생하거나 스택 오버플로우가 발생할 수 있다.) 따라서 아래의 코드에 시간초과가 발생하였다. 시간초과 코드 #define _CRT_SECURE_NO_WARNINGS #include int factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); } int main(void) { int n, k; int r..