붕어빵이 헤엄치는 바다

백준 1463번 문제. 1로 만들기 [Point] 다이나믹 프로그래밍으로 차근차근 부분해부터 구해나간다 자칫 막막해보일 수 있지만 다이나믹 프로그래밍의 관점에서 곰곰이 공략법만 제대로 짚어내면 쉬운 문제다. *변수 설명*N : 입력 변수DP[x] : x라는 숫자를 1로 만들기 위해 필요한 "최소 연산의 횟수". 1의 경우엔 0번의 연산, 2와 3의 경우엔 1번의 연산이면 충분하고 최종해를 구하기 위한 최소한의 기본해이므로 미리 초기화해준다. temp : 각각의 연산으로 나온 DP[x]의 값을 미리 저장하는 변수. 이 변수를 DP[x]값과 비교하여 더 작은 값을 DP[x]에 넣어준다 *알고리즘 설명* D[N] 은 다음 후보 중 가장 작은 값이 될 것이다.1번 후보. D[N-1] + 1 2번 후보. D[N/..

백준 1003번 문제. 피보나치 [Point] 문제 예제에 주어진 코드를 잘 활용하여 fib(1)과 fib(0)이 나올 때 카운트만 잘 해주면 된다. 쉬운 문제.예제로 주어진 코드를 조금 수정하면 된다. *변수 설명*cnt_0 : fib(0)이 몇 번 나오는지cnt_1 : fib(1)이 몇 번 나오는지T : 테스트 케이스 N : 입력 *알고리즘 설명*재귀함수 int fib(int n) 을 이용하여 n이 1과 0일 때는 카운트 횟수를 증가시켜주고 그 외의 경우에는 fib(n-1)과 fib(n-2)를 호출해주면 된다. 그림을 그려보면 이진트리처럼 내려가게 됨. 별 다른 설명은 더 필요 없을듯하다. 123456789101112131415161718192021222324252627282930313233#incl..

백준 2110번 문제. 공유기 설치 [Point] 파라메트릭 서치를 이용 (최적해 -> 이진탐색 + 결정) 공유기를 최대한 널찍널찍하게 설치할 수 있는 최대 거리를 찾는 문제다. 이진탐색의 응용 버전인 파라메트릭 서치를 이용하면 된다.간단한 개념은 이 게시글에 정리해두었으니 참조 알고리즘 자체는 어렵지 않다."음..좋아 너로 정했다!""문제 조건 만족!""헐..니가 만족된다구..? 좋아 일단 널 임시 정답으로 생각해둔 다음... 가라 다음 후보!""피카피카! 문제조건 만족!""헐 너도 만족되는구나! 가라 다음 후보!" 이렇게 이진탐색으로 범위를 좁혀가면서 최적해를 구하면 된다.(무슨 소리인지는 나만 이해할 수 있을 것 같다......) 기본 뼈대는 다음과 같다. 1. 필요한 값을 입력받고, 집의 위치를 ..

백준 2346번 문제. 풍선 터뜨리기 [Point] 원형으로 작동할 수 있게끔 하되, 는 것에 유의하여 "몇 걸음"을 움직였는지 카운팅해줄 것 처음에 이 문제를 보자마자 떠오른 생각은 환형 더블 링크드 리스트였다 (Circular Double Linked List) 터뜨린 풍선은 앞으론 고려 안한다는 점에서 원형 큐도 좀 생각하긴 했다..하지만 C언어에서 구현하려면 코드가 생각보다 길어질 것 같아서 어떻게 할까 고민하다가, 그냥 야매로 배열을 사용하기로 결정. 전체적인 알고리즘의 뼈대는 다음과 같다. Remain : 남아있는 풍선의 갯수 total : 전체 풍선의 갯수 (이 값은 변하지 않는다)dir : 방향move : 몇 걸음 이동해야 하는가 (속도 = 속력+방향인것처럼 arr[i]의 값을 몇걸음(mo..

백준 1005번 문제. ACM Craft [Point] DP와 DFS를 짬뽕시켜 풀어보자. 개인적으로 좀 고난에 빠졌던 문제.분명 알고리즘 분류에 "위상정렬"이라고 들어가있는데, 나는 위상정렬로 어떻게 풀어야할지 떠오르지 않아서 다이나믹 프로그래밍과 DFS를 짬뽕시켰다.찾아보니 이 분의 글이 "위상정렬" 관점에서 제일 설명이 잘 된 글 같다. (링크) 일단 목표건물 w부터 차례대로 역추적 DFS를 하려고 했다DP배열은 0으로 초기화되어있으니 visit 배열의 역할을 대체하여 사용하였다. 부분해의 후보들 중 가장 큰 값을 가진 후보가 부분해로 채택이 되고, 이런 부분해들이 모여 최종 해를 구할 수 있다 (건물을 시공하려면 선행건물이 전부 다 건설되어야하기때문에 가장 건설시간이 긴 선행건물을 생각해야한다) ..

백준 4963번 문제. 섬의 개수 [Point] DFS를 이용해 그래프의 연결요소(Connected Component)의 갯수를 찾아내라 그래프의 연결요소란 이동가능한 "뭉치"라고 생각하면 된다. 이 문제에서 요구하는 섬의 정의와 그 갯수는 그래프의 연결요소 개수와 일맥상통한다.우선 w=0,h=0이 들어오지 않는 이상 무한루프로 케이스를 입력받고 결과값을 출력하면 된다.매 과정이 반복될때마다 방문여부를 알려주는 visit[][]과 섬의 갯수를 알려주는 cnt 변수를 도로 초기화하는 것을 잊으면 안된다. 코드는 간단하다.방향배열 dx,dy를 이용해 탐색가능한 8개의 주변 정사각형을 검사한다.①이동가능하면서(map[][]=1) ②맵을 벗어나지 않는 유효한 범위(nx와 ny의 범위 체크), ③마지막으로 한번도..

백준 2178번 문제. 미로 탐색 [Point] BFS 알고리즘 활용, 레벨=거리 라고 생각한다 BFS 알고리즘은 시작 노드로부터 레벨 0, 1, 2, .... 순으로 순차적으로 탐색해나가는 그래프 순회 알고리즘이다.이를 이용해서, 이동가능한 주변 노드를 계속 탐색하다가 다음 탐색지에 목표 노드가 포착되면 해당 레벨에 1을 더해서(목표지점으로 한번 더 뛰어야하니까) 리턴해주면 된다.위에서 서술한 BFS 특성 때문에 맨 처음 리턴하는 레벨값이 '최소'거리일수밖에 없음.구조체를 이용, level 변수가 거리를 나타내는 변수라고 보면 된다. 처음에 헤맸던 부분은 level, 즉 거리를 어떻게 적어주냐였다. 처음엔 while문 안에 넣어서 한사이클 돌때마다 level을 늘려버리는 바람에 레벨 2에 있던 애들은 ..

백준 1260번 문제. DFS와 BFS [Point] 배열을 적절히 활용하여 인접여부를 나타내주는 인접행렬과 큐를 구현 C언어만으로 구현했다.기본적인 DFS와 BFS, 그리고 Queue의 개념만 잘 알고 있으면 문제없이 풀 수 있다.전역변수나 지역변수 선언은 그냥 입맛대로 알아서 선언했다. N은 전역변수로 들어가는게 더 이뻤을것같지만... DFSvisit,BFSvisit : 각 정점의 방문 여부(방문시 1, 미방문은 0)를 나타내주는 배열 변수. 어디에서 쓰냐에 따라 BFSvisit과 DFSvisit으로 구분해두었다Graph : 정점간의 연결 여부를 알 수 있는 인접행렬 (Adjacency Matrix). 인접리스트를 활용하는 방법도 있으나 구현의 용이성은 행렬 쪽이 좀 더 난 편하다queue : BFS..

백준 2439번 문제. 별찍기-2 포인트랄게 없다..for문만 알면 풀 수 있는 문제 123456789101112131415161718192021#include int main(){ int i,j,N; scanf("%d",&N); for(i=N-1;i>=0;i--){ for(j=0;j

백준 1924번. 2007년 [Point] 모드 연산 총 날짜(sum_days)를 계산하고 7로 나눈 모드 값을 구해서 매칭시키면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include int main(){ int month,day,x; int sum_days=0; scanf("%d%d",&month,&day); month--; while(month>0){ if(month==4 || month==6 || month==9 || month==11){ x=30; } else if(month==2){ x=28; } else{ x=31; } sum_days+=x; month..