공상하는 개발자

백준 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;..

이름만 들어도 어려울 것만 같은 다익스트라... 컴퓨터 과학자 에츠허르 데이크스트라 이름을 따서 만들었다고 한다. (나도 내 이름을 딴 알고리즘 만들고 싶다...ㅎㅎ) 어쨌든 어렵다고 생각했던 다익스트라를 파헤쳐보자!~ 레스 기릿 다익스트라 알고리즘이란? -> 간단하게 하나의 정점에서 다른 점들로 가는 최단경로를 구하고 싶을 때 사용한다. (최단거리를 구하고 싶을 때 사용!) 시작점을 D로 잡고 나머지 점까지의 최단거리를 구해보자. D는 출발점이기 때문에 최단거리가 0이므로 0으로 초기화한다. D를 제외한 최적경로는 아직 연결이 안 돼있으므로 무한대로 초기화한다. A B C D D INF INF INF 0 INF 위에서 현재 최단거리가 가장 짧은 노드를 고른다. D번 노드이다. D번 노드에서 뻗어나가는 ..