공상하는 개발자

항상 동적 프로그래밍 앞에만 서면.. 작아지는 나.. 이제는 그러지 않겠다는 마인드를 가지고!! 대대적인 DP 정복 포스팅을 시작해보자~ 첫 번째 주제는 메모이제이션 기법이다! 그렇다면 완벽한 DP를 위해 달려보자. 동적 계획법은 무엇일까? -> 복잡한 문제를 간단한 여러 가지 문제로 나누어서 푸는 방법. -> 중복된 부분을 제외하여 한번만 계산하고도 구할 수 있어서 시간, 공간 복잡도를 줄일 수 있는 장점이 있다. 피보나치를 구하는 두가지 방법 1. 재귀를 이용하여 그냥 구하기. -> 답은 나오지만 숫자가 커질수록 되풀이되는 함수가 많아져서 시간이 오래 걸린다. (시간 복잡도 : O(2^n)) static long fibo(int N) { if (N 한번 구한 계산은 더 이상 계산하지 않고 가져다 쓰는..

백준 1194 달이 차오른다, 가자 를 풀면서 방문 체크를 도대체 어떤 식으로 해줘야 할까라는 고민에 빠지게 되었다.. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net a~f까지의 열쇠를 어떻게 해주어 하냐 했는데, 비트 마스킹을 이용해 보라는 조언을 받았다.. 들어는 봤는데 자세히는 몰라서 한번 공부를 해보자 라는 생각으로 이번 블로그 포스팅을 쓴다.. 그럼 시작해볼까? 비트 마스크(BitMask) 란? 정수의 ..

투포인터 알고리즘을 소개하고자 한다. 코딩 테스트에 많이 나오는 유형이라서 알면 매우 좋을 것 같다. 그럼 고고~ 투포인터 알고리즘 투포인터는 선형 시간으로 알고리즘을 풀 수 있게 만들어주는 마법의 알고리즘이다. 하지만 매우 간단해서 구현도 할 만하다. 알기만 하면 그냥 써먹으면 된다! 투포인터는 연속적인 값들을 이용해 푸는 문제에 적합하다. 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 일단 백준 2003 문제를 읽고 오자. 간단하니까 금방 읽을 수 있다. 이 문제는 정수로 된 ..

모의 SW 역량테스트를 준비하면서 등산로 조성이라는 문제를 접하게 되었다.. 문제 링크는 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 와 같다. 초기 해결 방안 -> 처음 이 문제를 읽고 BFS로 풀어야겠다는 생각을 했다. 그 이유는 아직 DFS는 익숙하지 않고, BFS의 문제를 많이 접해봤기 때문이다. 이 문제는 BFS + 완전 탐색이라고 생각하였고 문제를 풀었다. 코드 (BFS + 완전탐색) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList;..