전체 글
9461번-파도반수열
문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 보면 누가봐도 규칙을 찾으라고 예시까지 친절하게 준다. 2) 시간 복잡도 완전탐색으로는 구현할 방법이 떠오르지 않는 문제. 삼각형의 예시를 보면서 점화식을 찾아야 하는 문제이다. 3) 배운 점 문제에서 n은 100까지 인데 문제를 보면서 규칙을 찾다보면 점화식이 cache[n] = cache[n - 2] + cache[ n - 3]인걸 알 수 있다. 그러므로 숫자..
1003번-피보나치함수
문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 피보나치 함수에서 재귀되는 경우에 0과 1이 몇 번 나오는지 물어보는 문제이나 반복된 재귀를 사용할 경우 시간초과 발생 2) 시간 복잡도 시간복잡도를 줄이기 위해 공통된 규칙이 있는 DP 방법을 탐색 n= 0 일 때 zero는 1개 나오고 one은 0개 나온다 n= 1 일 때 zero는 0개 나오고 one은 1개 나온다 n= 2 일 때 zero는 1개 나오고 one은 1개 나온다 n= 3 일 때 zero는 1개 나오고 one은 2개 나온다 n= 4 일 때 zero..
10816번-숫자카드2
문제 https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=10816&from_mine=1 채점 현황 www.acmicpc.net 접근방법 1) 접근 사고 https://hyeophyeop.tistory.com/18 문제와 같습니다. 다만 갯수를 추가 해줘야 하므로 equal_range방식 또는 단순 구현으로 풀이를 해야한다. 2) 시간 복잡도 https://hyeophyeop.tistory.com/18 참조 3) 배운 점 복습하는데 좋았다! 4) PS 3가지 방법으로 구현해보았습니다. equal_range로 구현할 때 이유는 모르겠으나 배열을 사용하여 연산하니 오답처리를 받아서 Vector를 활용하는 방법으로 변경했습니다. 아무래도 메모리를 확보하..