목록2017/11 (19)
Inor
- 연결 리스트 연결 리스트(Linked List)는 배열과 같이 스택, 큐 등 자료 구조들의 기반이 될 수 있는 자료 구조입니다. 연결 리스트는 정보를 담고 있는 노드와 각 노드들의 논리적인 연결로 구성됩니다. 노드는 정보를 구성하는 데이터와 다음 노드와의 논리적인 연결을 지원하는 변수로 구성됩니다. 변수는 C 언어의 포인터와 같은 개념으로 정의 되고 변수에는 다음 노드의 주소값이 할당됩니다. head는 첫 node의 주소값을 갖고 있는 변수입니다. head는 연결 리스트의 각 노드를 방문하기 위한 첫 시작이라고 할 수 있습니다. head의 값을 잃어버린다면 그 리스트에 다시 접근하는 것은 불가능합니다. 그리고 이 연결 리스트는 메모리 어딘가에 표류하게 됩니다. 각 node는 자료 구조(연결 리스트)를..
화재가 발생한 빌딩(2차원 배열)에 갇힌 사람을 탈출 시키는 문제 입니다. 불이 옮기는 시점과 사람을 이동시키는 시점을 잘 분류해서 쉽게 해결하였습니다. BFS를 이용해서 사람이 이동 가능한 위치를 찾아서 이동 시키고 화재가 퍼질 수 있는지 확인하여 불이 번지도록 만들었습니다. 사람이 탈출 할 수 있는 최단경로를 찾아야하기 때문에 BFS를 사용 하였습니다. 아래는 문제 링크와 소스 코드 입니다. https://www.acmicpc.net/problem/5427 import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class EscapeFireBuilding ..
안전 영역 문제는 장마철 비가 어느정도 왔을때 안전영역의 갯수가 최대가 되는지 구하는 문제 입니다. 강수량을 확인해서 침수 영역을 만들어주었습니다. 그 후에는 안전구역을 BFS 알고리즘을 사용해서 확인 했습니다. 더 이상 탐색할 곳이 없다면 안전 구역의 번호를 1 증가 시키고 다음 영역을 탐색하였습니다. 처음에는 안전구역이 가장 넓은 경우를 찾는 문제라고 생각했고 비가 가장 조금 왔을 경우에 안전구역이 넓어질 것이라고 생각했습니다. 그러나 안전 구역의 넓이가 아니라 안전 구역이 만들어진 갯수의 최댓값을 구하는 문제인 것을 확인하고 강수량이 될 수 있는 1부터 100까지 모든 경우에서 확인을 하였습니다. 프로그램의 실행 시간을 조금이라도 줄일려면 입력된 구역에서 가장 높은 위치의 값과 강수량을 비교해서 가..
테트로미노 문제는 2차원 배열에 테트리스 게임에서 나오는 막대 모양을 올려 놨을때 해당 위치의 값들을 더해서 최댓값을 찾아내는 문제 입니다. 테트리스에 나오는 막대 모양은 회전, 대칭이 가능하다고 문제에서 설명해주고 있습니다. 해당 문제는 DFS를 이용해서 풀었습니다. 모든 막대기를 만드는 블록들이 총 4개라는 공통점을 찾았고 4번씩 이동했을때 모든 테트리스의 막대기 모양이 만들어진다는 것을 직접 그려가며 발견하였습니다. 4번 이동했을 경우에 1번, 2번, 3번, 4번째에 탐색된 위치의 값들을 더해서 최댓값과 비교하였습니다. 그러나 여기서 한가지 예외 상황이 있었는데 ㅗ모양의 막대기는 DFS를 이용해서 해결할 수 없다는 문제를 발견하였습니다. 이유는 중간에 3갈래 길이 생기는데 재귀함수를 이용해서 모든 ..
2차원 배열에 위치한 토마토가 4방향(동, 서, 남, 북)으로 퍼지면서 주변에 토마토들이 익어가는 문제 입니다. 전형적인 BFS 문제이라고 판단하였고 BFS를 이용해서 문제를 해결하였습니다. 초기에 입력된 정보에서 토마토의 위치를 큐에 넣어두고 BFS탐색을 시작하였습니다. 토마토가 이미 익었을 경우와 벽이 있는 경우에는 큐에 넣지 않았고 익지 않은 토마토를 큐에 넣고 현재 위치의 토마토가 익은 날짜 +1을 해서 몇일째에 토마토가 익었는지 2차원 배열에 표시하였습니다. 아래는 문제와 소스 코드 입니다. https://www.acmicpc.net/problem/7576 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..
연구소에 바이러스가 퍼지지 못하게 3개의 기둥을 세워서 피해를 최소한으로 만드는 알고리즘 문제 입니다. 탐색(BFS, DFS)에대해서 공부해야겠다는 생각을 갖도록 만들었던 문제 입니다. 처음에는 어떻게 접근해야할지 감도 못잡았는데 탐색에대해 공부하니 어렵지 않게 풀 수 있었습니다. 아래는 문제의 링크 입니다. https://www.acmicpc.net/problem/14502 3개의 기둥을 세우는 방법은 재귀 함수를 만들어서 해결 했습니다. 3개의 기둥이 모두 세워졌을때 BFS탐색을 이용해서 벽이 아닌 곳으로 바이러스를 퍼뜨렸습니다. 그리고 바이러스가 퍼진 연구소를 다시 원상 복귀 시키며 바이러스가 퍼지지 않은 부분을 계산하였습니다. 문제를 풀면서 아쉬웠던 부분은 기둥을 세우는 부분의 재귀 함수를 조금 ..