나아가는중

백준 Baekjoon 16954번 움직이는 미로 탈출 - JAVA 문제 풀이 BFS탐색을 사용하여 캐릭터를 이동 시킨다. 최초에는 처음 시작위치인 7,0을 넣고 시뮬레이션을 시작한다. 큐에서 캐릭터를 현재 케릭터들의 위치들을 꺼내와 9방향으로 이동할 수 있는지 검사하고 새로운 위치를 큐에 추가한다. 큐의 사이즈만큼만 반복하여 큐에서 캐릭터를 꺼내면 새로 추가되는 위치는 탐색하지 않게 된다. 동일한 위치에 여러 캐릭터가 이동하는 것을 방지하기 위해 visit배열을 둔다. visit배열은 매 턴이 끝날때 마다 새로 생성되어야 한다. 이전에 있었던 위치로 돌아가야 하는 상황도 존재한다. 새로운 위치로 이동시켜 큐에 추가한 위치가 벽이 이동하면서 벽과 겹쳐질 수 있어 큐에서 꺼냈을 때 검사해야 한다. 케릭터 이..

[백준 Baekjoon] 14719번 빗물 - JAVA 문제 풀이 특별한 알고리즘의 사용은 없는 구현을 사용한 문제이다. 빗물이 고이는 두가지 경우를 생각하여 각각 구해줌으로 문제를 풀었다. 1 왼쪽 기둥보다 오른쪽의 기둥이 큰 경우. 좌에서 우로 순회한다. 1.1 왼쪽 기둥의 높이를 h, 위치를 left에 저장하였다. 1.2 왼쪽 기둥보다 오른쪽 기둥이 큰거나 같은 경우 양 기둥 사이를 순회하며 두 기둥중 작은 기둥의 높이에서 뺄셈을 한다. 1.3 왼쪽 기둥과 위치를 새로 최신화 해준다. 2 왼쪽 기둥보다 오른쪽의 기둥이 작은 경우. 우에서 좌로 1에서 구한 마지막 왼쪽 기둥까지 순회한다. 2.1 1에서 구한 마지막 왼쪽 기둥까지의 빗물을 계산이 완료되어 마지막 왼쪽 기둥까지만 한다. 2.2 오른쪽 기..

** 백준 Baekjoon 16974번 서울 지하철 2호선 - JAVA 문제 풀이 주어진 입력으로 그래프를 만들었을 때, 순환선(사이클)과의 거리를 각 역마다 출력하는 문제이다. 그래프에서 사이클을 찾는 것이 가장 중요하다. 사이클을 찾고 사이클에서 각 역이 얼마나 떨어져 있는지 찾아 문제를 해결하였다. 사이클을 찾는 여러 방법이 있을것이다. 각 역마다 사이클을 점검하는 방법을 처음 생각하였는데 그러면 비용이 클것 같아 한번에 사이클을 찾는 방법에 대해 생각해보았다. 빽트래킹과 유사하게 스택을 사용하여 문제를 해결하였다. 각 역을 방문할 때에 스택에 추가한다. 방금 전 방문한 곳이 아니며 이전에 방문한 경우 사이클이 발생한다. 스택에 사이클의 시작점을 추가한다. 사이클을 체크할때 해당 역이 다시 나올때까..

컴퓨터 네트워크 - Web and HTTP (Application layer) Web Page 웹 페이지는 오브젝트로 구성되어 있다. 오브젝트는 HTML file, JPEG image, Java applet(소형 프로그램), audio file 등이 될 수 있다. 웹 페이지는 기본적인 HTML-file에 여러 참조 오브젝트를 포함하고 있다. 각 오브젝트는 URL로 지칭된다. 예시로 www.dlee0129.tistory.com/manage/posts에 www.dlee0129.tistory.com는 호스트 네임에 해당하고, /manage/posts 는 path(Object URL) name이다. HTTP Overview HTTP(Hypertext Transfer Protocol)은 서버 HTTP 프로그램과 ..

백준 Baekjoon 16235번 나무 재테크 - JAVA 문제 풀이 구현, 시뮬레이션으로 분류된 문제이다. 문제 설명을 잘 읽고 정리하여 따라 하는것으로 풀 수 있다. 풀이에 대한 설명보다 코드의 주석을 보는것이 이해가 쉬룰 것이다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..

백준 Baekjoon 2749번 피보나치 수 3 - JAVA 문제 풀이 피보나치 수의 개념을 알고 여러 문제들을 풀어봤지만, 이번 문제처럼 큰 입력은 처음으로 주어졌다. 메모리제이션을 하고 최대한 시간초과가 나지 않게 하려 해도 불가능하여 검색을 해보니 피사노라는 피보나치의 속성이 있고, 이를 활용하여 문제를 풀 수 있었다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

백준 Baekjoon 15684번 사다리 조작 - JAVA 문제 풀이 구현 + dfs + 완전탐색 문제이다. 문제가 길고 복작해서 정말 읽기 싫은 문제였다. 최대 사다리를 3개까지 놓아 i번째 사다리가 i번으로 가게 만드는 문제이다. 사다리를 입력 받을 때 양측 통행{(x,y), (x,y+1)}이 가능하도록 놓는 것이 편하다. i번에서 i번 탐색 시 좌 우 어느 방향으로 이동해야 하는지 알 수 있으며, 이렇게 하면 검사시 두 점을 검사하는 것으로 두 가로선이 연속하거나 접하지 않게 놓을 수 있다. 사다리를 최대 3개까지 놓을 수 있어 0 ~ 3개를 놓는 경우를 dfs로 검사한다. dfs 탐색 시 이미 검사한 가로선 위치(i)를 매번 검사하지 않도록 i = h에서 검사하게 한다. x는 세로 높이가 되고 y..

백준 Baekjoon 14890번 경사로 - JAVA 문제 풀이 어떠한 알고리즘을 적용하는 것이 아니라 구현을 통해 풀어야 하는 문제이다. 입력받은 지도에서 모든 행과 열을 검사하여 경사로를 놓아 길을 지날 수 있는지 검사해야 한다. 다음 칸과의 높이 차가 1이상인 경우 경사로를 놓을 수 없다. 내리막길인 경우(현재 칸 - 다음 칸 = 1), 오르막길인 경우(다음 칸 - 현재 칸 = 1) 경사로를 놓기 위해 필요한 L개의 칸을 검사하여 경사로를 놓을 수 있는지 검사한다. 1 내리막길인 경우 다음 칸부터 다음 L개의 칸을 검사한다. 2 오르막길인 경우 현재 칸부터 이전 L개의 칸을 검사한다. 이미 경사로를 놓은 칸에 경사로를 놓을 수 없다. 소스 코드 import java.io.BufferedReader;..

백준 Baekjoon 16236번 아기 상어 - JAVA 문제 풀이 문제에 있는 조건들을 잘 정리하고 bfs를 활용하여 먹을 물고기를 찾으면 풀리는 문제이다. 문제 설명이 길고 조금 복잡하여 조심히 풀어야 한다. 자세한 풀이는 소스 코드에 주석으로 하겠습니다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws ..

[백준 Baekjoon] 1700번 멀티탭 스케줄링 - JAVA 문제 풀이 그리디 알고리즘을 활용하여 해결할 수 있는 문제였습니다. 멀티탭이 모두 사용중인 경우에 가장 마지막으로 사용되는 콘센트를 찾아 제거하는데 그리디 알고리즘이 사용됩니다. 멀티탭에 꽃혀있는 전기용품을 HashSet을 사용하여 저장하도록 하였습니다. 멀티탭에 콘센트가 전부 사용중이기 전까지(HashSet size < N) HashSet에 추가해줍니다. 멀티탭의 콘센트가 전부 사용중인 경우 남은 전기용품을 순회하여 사용중인 전기용품 중 앞으로의 순서(list)와, 사용하지 않는 전기용품(remain)을 찾습니다. 이 경우 플러그를 빼는 것이므로 answer를 1증가 시킵니다. 전부 사용중인 경우 순서에서 가장 마지막으로 사용될 전기용품을..