백준 문제풀이(JAVA) (26) 썸네일형 리스트형 백준 15686번(JAVA) brute force 문제이다. 시간초과때문에 몇 번이고 다시 풀었던 문제이다. 시간초과를 피하며 구현을 잘하면 된다 이 문제의 핵심은 3가지라고 생각한다. 지도를 입력받으며 치킨집과 가정집의 위치를 미리 선언한 ArrayList에 넣는다. ArrayList를 사용함으로써 지도 전체를 탐색하며 거리를 계산하는게 아니라 ArrayList에서 각각 꺼내와서 거리를 계산한다. 이러면 시간을 훨씬 단축시킬 수 있다. 치킨집 ArrayList에서 M개의 치킨집을 고르는것은 backtrack으로 구현한다. 만약 백트랙하다가 치킨집의개수가 M개가 되면 바로 DFS()함수를 호출해서(이름은 그냥 막 지었다) M개의 치킨집에대한 치킨거리를 구한다. Backtrack을 할때 재귀함수로 호출하는데 호출할때 시작점은 이전에 .. 백준 1103번(JAVA) 이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다. DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다 왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다. DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다. 소스코드 import java.io.*; import java.util.*; public class Main { public static int N; public static i.. 백준 1826번(JAVA) 아래 문제와 매우 비슷하다. 우선순위큐에 객체를 넣어서 객체끼리 비교할 줄 알면 수월하게 풀 수있다. 아래 문제도 같이 참고해서 보면 비슷한 유형이라는걸 알 수 있다. 2021.04.30 - [백준 문제풀이(JAVA)/그리디 알고리즘] - 백준 1781번(JAVA) 백준 1781번(JAVA) 처음엔 이 문제를 그리디 알고리즘에 넣어야 하나, 우선순위 큐 카테고리로 넣어야 하나 고민했다. 근데 뭐 큰 의미없는 거 같아서 걍 그리디 알고리즘에 넣는다. 처음에는 그냥 단순히 마감시 red-tiger.tistory.com 우선 입력값을 거리가 가장 작은게 앞에오도록(우선순위가 크게) 정렬한다. 이중 while문을 사용한다 첫 번째 while문에서는 (현재가지고연료 백준 1781번(JAVA) 처음엔 이 문제를 그리디 알고리즘에 넣어야 하나, 우선순위 큐 카테고리로 넣어야 하나 고민했다. 근데 뭐 큰 의미없는 거 같아서 걍 그리디 알고리즘에 넣는다. 처음에는 그냥 단순히 마감시간이 적은것이 큰 우선순위를 갖도록, 그리고 마감시간이 같다면 컵라면 개수 많이주는걸 우선순위가 크게 우선순위큐에 넣었다. 예제는 잘 통과했는데 바로 틀렸다. 이유는 만약 문제가4개라 할떄 문제번호 1 2 3 4 데드라인 1 1 2 2 컵라면 개수 10 20 100 100 이런 경우에서 자연스럽게 데드라인 1중 컵라면개수가 더 많은 20을 택한다. 그리고 흘러간시간을++해준다. 그 후, 데드라인 2중에서 하나를 택해서 100을 골라서 총 컵라면개수는 120개가 된다. 하지만 사실 처음에 3번을 풀고 그 다음에 4번을 풀면.. 백준 14267번(JAVA) 기본적으로 트리를 생성할 줄 안다면 수월하게 풀 수있다. 나 같은경우에는 ArrayList로 트리를 구현했다. 문제에서는 직속부하와 상사라고 표현했지만 직속부하는 자식 노드, 상사는 부모 노드, 사장은 루트노드라고 생각하고 풀면된다. 우선 부모자식 관계를 입력받는다. 그 후 따로 선언해놓은 int[] result배열에 각각의 칭찬수치를 더한다. 예를들어 2번직원이 2만큼 칭찬받았다면 result[2]=result[2]+2, 3번직원이 4만큼 칭찬받았다면 result[3]=result[3]+4, 이런식으로 그 후 사장노드부터 DFS를 실시하는데 실시할때 부모노드의 result값을 자식노드의 result값에 더한다. 그리고 result를 1부터 n까지 출력하면 끝. 핵심은 DFS를 사장부터 시작하고 부모노드.. 백준 10282번(JAVA) 기본적인 다익스트라 문제이지만 원하는 값은 다르다. 정점의 개수가 주어지고 출발점에서 시작해서 도달 할 수 있는정점은 몇개인지(시작점 포함), 그리고 도달 할 수있는 정점중 가장 거리가 먼것은 몇인지 출력하면된다. 간단하게 일반적인 다익스트라를 실시한다. 일반적인 다익스트라에 관한 문제는 아래에 링크를 걸어두겠다. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 단순하게 시작점에서 해당 정점까지의 거리를 나타내.. 백준 11779번(JAVA) 이번 문제는 다익스트라 알고리즘에다가 되추적까지 해줘야 하는 문제다. 문제의 조건에는 안나와있지만 정점은 1번부터n번이다. 기본적으로 다익스트라와 동일하다. 단, 되추적을 위해 int[] before 배열을 선언한다 예를들어 최단거리 경로가 1번에서 3번으로 가기위한 최단 경로가 1->2->3일경우 before[3]=2, before[2]=1을 집어넣는다. 되추적은 일단 index를 end로 잡는다 그리고 루프를 돌면서 index를 스택에 넣고 index=before[index] 실시하고 count값을 증가시켜준다. 만약 index가 start가면 루프를 깬다. count값을 출력하고 stack이 빌 때까지 계속 출력해주면 된다. stack에는 처음에 index를 집어넣으면 end가 들어가고 마지막에는 .. 백준 1261번(JAVA) 다익스트라를 응용하는 문제이다. BFS와 다익스트라를 모두 다룰줄 안다면 손쉽게 풀 수 있다. 기본 다익스트라를 모를 경우 아래 링크에서 참고하도록 하자. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 일반 다익스트라와 다른점을 꼽자면 굳이 연결정보를 안알려준다는 것이다. 나는 단순하게 생각했다. 현재정점의 위,아래,오른쪽,왼쪽은 모두 연결되어있으며 만약 벽이 있다면 가중치가 1,벽이 없다면 가중치가 0.물론.. 이전 1 2 3 4 다음