Hailey

| 문제 해결방법 BFS (+ 사방탐색 가능 여부 체크) 이 문제는 단순한 BFS문제이다. BFS로 탐색하면서 주어진 시간만큼동안 이동할 수 있는 위치의 개수를 출력해주면 된다. 단, 터널의 모양에 따라 다음 위치로의 이동 여부가 결정된다. 터널은 1번부터 7번까지 다 다른 모양을 가지고 있다. 상, 우, 하, 좌 순서로 터널 모양에 따라 이동 가능한 방향은 true, 이동이 불가한 방향은 false로 저장한 deltas 배열을 사용하였다. (터널이 1~7번까지 있기 때문에 0번째 열은 자리를 채워주기 위해 임의로 준 값- 사용하지 X) static boolean[][] deltas = { { false, false, false, false }, { true, true, true, true }, // 1..

최근에 백준에서 동일한 문제를 푼 기억이 있어서 금방 풀었던 문제이다. 백준 4485번 녹색 옷 입은 애가 젤다지? 링크 : https://www.acmicpc.net/problem/4485 | 문제 해결방법 다익스트라 + 우선순위 큐 ★다익스트라 알고리즘과 우선순위 큐(Priority Queue)를 함께 사용하면 효율이 극대화된다. [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; class node implements Comparable{ int r, c, cost; public node(int r, int..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 비트마스킹에 대한 글을 포스팅 한 후 금방 터득한 생생한 지식으로 바로 풀어보았다✨ | 문제 해결방법 부분집합 구하는 공식 + 비트마스킹 부분집합을 구할 때 1. boolean배열을 사용할 수도 있고 2. 비트마스킹 기법을 사용할 수도 있다. 이번 문제에서는 비트마스킹 기법을 사용하였고, 이 기법은 비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아..

목차 1. 비트마스크란? 2. 비트마스크의 예시 3. 비트 연산자 | 비트마스크(Bit Mast)란? 비트마스크는 알고리즘이 아닌 하나의 기법으로 정수를 이진수로 표현하고, 비트연산으로 다양한 문제를 해결해나가는 방법이다. | 비트마스크 예시 예를 들어 열쇠가 a , b , c , d , e , f로 6개가 있다고 가정한다. 이때, 가지고 있는 열쇠가 a , c , e 일때, 위와 같이 표현할 수 있다. 이 예시에서는 열쇠를 가지고 있는 경우/가지고 있지 않은 경우(1/0) 를 비트마스크로 표현하였는데, 이 경우 이외에도 스위치를 켜거나 끄는 경우, 해당 위치에 방문했거나 아직 방문하지 않는 경우 등 더욱 다양한 상황에서도 적용이 가능하다. 여기서 알 수 있는 점은 비트마스크는 이진수를 이용하여 두 가지..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net | 문제 해결방법 이 문제는 제목에서 대놓고 힌트를 주고 있다. 플로이드-워셜 알고리즘으로 문제를 풀면 된다. 기본적인 플로이드-워셜 문제와 거의 동일하다. 한 가지 다른 점은 예제를 한 번 손으로 적으면서 돌려보면 알 수 있는데, 같은 간선에 비용만 다른 경우가 존재한다. 이 경우 우리가 하려고 하는 값은 최소 비용이기 때문에 작은 비용을 선택해주면 된다. 그리고 내가 두 번이나 틀렸던 이유로 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs + 인접행렬 1. 입력받은 네트워크 쌍을 이용해 인접행렬을 초기화 한다. 2. (1,1) 부터 시작하여 네트워크로 연결되어 있는 컴퓨터를 모두 탐색한다.( bfs + visited[] ) 3. visited[] (방문한 컴퓨터는 true가 됨) 배열에서 true의 개수를 반환(1번 컴퓨터는 counting하지 않음) [JAVA] 해설 코드 import java..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net | 문제 해결방법 개인적으로 굉장히 쉬운 문제였다. 단지별로 단지 번호, count만 잘 처리해주면 인접리스트 + bfs로 쉽게 해결 관련 알고리즘 : 인접리스트 + bfs [JAVA] 해설 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arra..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : bfs (dfs로 시간초과가 난 후 방법을 bfs로 변경) 인접행렬 * O(V^2) 인접리스트 * O(V+E) 처음에 인접행렬 + dfs로 풀 방법은 시간초과 이후 인접리스트 + bfs로 방법을 바꾸어 풀어서 해결했다. [JAVA] 해설 코드 1. 인접행렬 + dfs (시간초과) package graph; import java.io.BufferedReade..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net | 문제 해결방법 관련 알고리즘 : DP 규칙 찾기 나의 풀이 방법은 n이 홀수인 경우와 짝수인 경우를 나누어 계산한다. n=1인 경우는 단 한 가지 n=2인 경우는 세 가지 n=3인 경우 n이 홀수일 경우의 규칙은 바로 전에 구한, n=2일때의 타일들에 맨 앞, 맨 뒤에 하나의 타일을 붙여주는 것이다. 이 경우 2x1 타일로만 이루어진 경우가 중복해서 나오기 때문에 -1을 해준다. f(3) = f(2) * 2 - 1 n=4인..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net | 문제 해결방법 이 문제를 푸는데 약 두 시간이 걸렸다. 최대한 힌트를 참고하지 않고 풀어보려고 노력했더니 더 공부가 많이 되었다. 그리고 DP문제는 어떤 값을 메모제이션 할 것인지를 결정하는 것이 굉장히 중요한 것 같다. 1. 첫 번째로 고려할 점 처음에는 dp배열에 계단수의 시작되는 수가 index인 위치에 각 경우의 수를 넣어주었다. f(1) 인 경우, 0으로 시작되는 수만 제외하면 1부터 9까지 각각 자신의 수로 수를 만들 수 있다. 그래서 경우의 수는 f(1) 0 1 2 3 4 5 6 7 8 9 0 ..