키큰개발자

문제링크 : https://www.acmicpc.net/problem/7490

해결방법 : 

1 부터  N까지 -, +, " " 의 연산을 사이에 각각 넣어서 최종 합이 0이 되는 식을 모두 출력하는 문제다.

일단 식을 누적하는 변수 str, 최종합을 누적하는 변수 sum을 설정하고 생각해봤다.

자연스레 3가지경우에 대해 재귀호출을 하면 모든 경우를 만들 수 있기에 3가지의 재귀함수를 설계하면 답을 구할 수 있다.

여기서 ""연산에 대해 주의할 점이 있는데, 

다음 재귀에 +나 -를 만나면 이전의 값(num)을 sum에 더해주거나 빼준다. 그전에는 sum에 아무런 계산하지 않는다.

이말은 ""로 된부분은 num에 합쳐진숫자로 업데이트만 하고, 다음에 +나-가 오면 계산을 해준다는 것이다.

나머지 -, +의 경우에는 다음에도 -,+일때 sum에 num*sign 값을 더해준다. 참고로 sign을 곱해주고 더해주면서 뺄셈을 한다. 

재귀함수로 넘겨주는 값을 보면 이해가 될것이다.

소스코드)

문제 링크 : https://www.acmicpc.net/problem/1003

해결 방법 :

피보나치 함수를 재귀함수, Top-down 방식으로 푼다고 했을 때 fibonacci(0), fibonacci(1) 의 호출 개수를 각각 출력하는 문제다.

처음에는 단순히 

if(n == 0) 일때 0의 카운트 증가,

if(n == 1) 일때 1의 카운트 증가로 바로 풀수가 있었는데 채점해보니 시간초과가 떴다.. ㅋ

아 그러면 익히알고있는 다이나믹프로그래밍으로 메모를 쓰고 읽어서 시간을 줄여야 되는 구나라고 생각했다.

테스트 케이스를 가지고 여러번 하다보니 다음과 같은 규칙을 발견했다.

N의 0호출 개수는 N-1의 1호출 개수라는 것

example)  5의 0의 호출개수 = 4의 1의 호출개수, 다른것도 직접해보면 알것이다.

따라서 N과 N-1의 피보나치함수를 호출하고 N==1일때 1의 카운팅을 리턴하여서 각각 총 1의 호출개수를 각각 구할 수 있었다. 

이때, 재귀함수에서 여러 N의 1의호출개수를 메모로 저장해둬서(d[N]) 시간을 줄였다.

소스코드)

문제링크 : http://codeup.kr/JudgeOnline/problem.php?id=1905

해결방법 :

정수 n이 입력으로 들어오면 1부터 n까지의 합을 재귀함수로 구현해야한다.

따라서 재귀함수를 구현하기 위해 다음을 설계해야한다.

1.기저조건

2.재귀처리구문 

기저조건은 입력 n이 1이하인 것이고 그때는 n을 리턴한다.

재귀처리는 n(현재 숫자) + f(n-1) (하나 전의 숫자까지의 1부터 총합) 을 하면 우리가 구하고자하는 1부터 n까지의 합을 구할 수 있다.

여기서 재귀함수인 f(n-1)은 우리가 원하는 값을 리턴해준다는 것을 가정해두고 설계한다. (실제 직접따라 들어가보면 값을 구해준다. 신기신기)

이렇게 가정하고 설계해도 답을 구하는 것은 귀납적인 식으로 설정해두었기 때문에 오류가 안나는 것이다.

그 이유는 기저조건을 세웠고(처음오는 자연수에 대한 증명), f(n-1)과 f(n)은 같은 방식(n이만족되면 n+1도 맨족..)으로 구해나가기 때문에 귀납적 증명을 한 것과 동일하기때문이다. 

다음 수학 귀납법 설명 참조

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.

1. 처음 오는 자연수(0 또는 1)에 대한 증명
2. $${\displaystyle n}이 만족시킨다는 가정 아래, $${\displaystyle n+1}에 대한 증명

소스코드)

문제 링크 : https://www.acmicpc.net/problem/1065

해결 방법 :

문제를 보면 각 자리 숫자가 등차수열을 이루는 것을 한수라고 했다.

testcase를 보고 처음에 조금 이상했는데 그 이유는 1,2,3,4,5,6과 같은 숫자도 등차수열로 카운팅 됫다는 점이다. 

일의자리숫자들은 등차라는 것이 없는 것인데.. 무튼 0의 등차가 있다라고 생각하고 이것만 예외로 생각하고 나면

간단하게 나머지 숫자들은 자리수를 각각 추출해서 등차가 같은지만 확인해서 카운팅 해주면 한수의 수를 구할 수 있다.

(참고)백의자리수 - 십의자리 == 십의자리 - 일의자리 

소스코드)

문제 링크 : https://www.acmicpc.net/problem/1110

해결방법 :

문제에서 주어진 규칙대로 새로운 수를 만들기위해 몇번 반복 하는지를 세어주면 답이다.

1. 새로운 수를 십의자리와 일의 자리로 나눈다.

2. 나눈 수를 더한다. (십의자리숫자 + 일의자리숫자) 

3. 1번에서 구한 일의 자리와 2번에서 구한 수의 일의 자리 값을 붙인다. 즉 새로운 수를 구한다.

   (붙인다는 것은 1번의 일의자리를 10의자리로 만들기위해 * 10 한 후  2번에서 구한 일의자리를 그대로 더하면 된다.)

4. 1~3번을 반복한다. 새로운수가 처음 주어진 수와 같을 때까지!  

이때, 싸이클 횟수가 답이기 때문에 반복 할때마다 카운트를 하나씩 증가해준다.

소스코드)

문제 링크 : https://www.acmicpc.net/problem/2448

해결방법 : 

삼각형 형태를 보면은 똑같은 부분이 3개위치에서 반복해서 그려지는 것을 볼 수 있었다.

맨위의 꼭짓점기준 1개 (하나의 삼각형 모습을 보이고 있다.)

맨위에서 왼쪽 아래에 있는 꼭지점 상단 1개 (하나의 삼각형 모습을 보이고 있다.)

맨위에서부터 오른쪽 아래에 있는 꼭지점 상단 1개 (하나의 삼각형 모습을 보이고 있다.)

이때 최소 단위의 형태는 3개의 높이의 별 삼각형 모습이고 이것을 기저조건으로 세운 후 높이가 3이되면 별을 찍어준다.

그리고 위에서 나눈 3개의 기준 좌표를 재귀함수로 넘기면서 각위치 마다 삼각형을 전부 그려준다.

따라서 재귀함수를 전부 돌면서 최소단위인 별 삼각형을 전부 찍어주면서 재귀가 끝난후 출력해주면 답을 구할 수 있다.

소스코드)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWaJ3q8qV-4DFAUQ&categoryId=AWaJ3q8qV-4DFAUQ&categoryType=CODE

해결방법 :

문제 지문이 짧고 난이도가 d3라 쉬울 것같았지만 쉽게 풀리지 않았던 문제였다.

아름답게 풀기위해 어떤 규칙성과 어떤 로직으로 짤지 고민을 하다가 시간이 많이 지체되서 그냥 무식하게 풀자는 생각을 했다 ㅋㅋ;

나의 아이디어는 다음과같다.

1. 1차원 배열 table에 소수를 미리 체킹해둔다.

2. n = a+b+c 이므로 a,b를 2중 for문 돌리면서 각 숫자가 소수인지 아닌지를 미리 기록해둔 table을 보면서 확인했다. (c는 a,b 정해지면 자동적으로 구하니 for문 안돌림)

3. 여기서 중복된 경우는 제외해줘야 하므로 visit 2차원배열을 만들어서 a,b,c의 중복된 경우를 제외해주었다. (testcase 결과값보면 중복된걸 제외해주었음)

소스코드)

문제 링크 : https://www.acmicpc.net/problem/1966

해결방법 :

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

문제의 조건 그대로 알고리즘을 설계하면 답을 구할 수 있다.

맨앞에 요소보다 뒤에 큰값이 없다면 그대로 queue에서 제거하면서 빼낸다.

아니라면 queue에서 맨앞에 요소를 뒤로 옮겨준다.

이걸 구현하기 위해서 앞에 추가삭제, 뒤에 추가삭제가 용이한 STL의 dequeue 자료구조를 사용했다.

그리고 찾고자 하는 문서정보를 가지고 있어야하기에 pair도 사용하였다. (second 요소 : 원래 주어진 인덱스위치)

문제링크 : https://www.acmicpc.net/problem/7576

해결방법 : 

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 

이 문제에서 주어진 설명을 보면 하루마다 익은 토마토 좌표를 기준으로 인접한 네 방향에 안익은 토마토를 익게하므로 BFS탐색 방법을 사용하기로 생각했다. 테스트케이스에서 익은 토마토를 기준으로 따라 그려나가다 보면 이해하기 쉬울 것이다.

따라서 상자에 있는 토마토 모두가 익는데 최소의 일수는 BFS 탐색을 하고난 후의 최종적인 depth(깊이) 값이다. (그림참고)

프로그램 로직은 크게 bfs 탐색 전후로 나눌수있는데,

탐색 전에서는 입력을 받는 가운데 map에서 -1값을 갖고있으면 해당 좌표를 방문처리를 미리 해버렸다.그리고 1값을 가진 토마토 익은 기준좌표를 queue에 넣고 이좌표 또한 방문 처리를 해준다. 그리고 한번 전체를 탐색해서 이미 다 익었는지를 확인하고 다익었으면 0을 출력하고 아니면 bfs 탐색을 시작하게 했다.

bfs를 탐색한 후에는 visit배열을 보고 0이 하나라도 남아있다면 -1 출력하고 아니라면 bfs탐색에서 구한 depth값을 출력했다.

소스코드)

문제 링크 : https://www.acmicpc.net/problem/2839

해결 방법)

Nkg 무게를 5kg과 3kg봉지로 최소로 가져가야 됬기에 5kg을 기준으로 최대 많이가져갈 수 있는 N/5 부터 0(5kg없는거) 까지의

모든 경우의 수를 제시하고 그에따라 3kg 봉지로 나눴을때 나머지가 0이면 답을 구할 수 있다.