본문 바로가기

Java128

[프로그래머스] Lv.1 바탕화면 정리 JAVA 풀이 문제 Lv.1 바탕화면 정리 (배열 탐색)  : 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판   컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 = wallpaper   빈칸은 = "."   파일이 있는 칸 = "#"   최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우기   드래그는 "점 S에서 점 E로 드래그한다"    "드래그 한 거리" = |rdx - lux| + |rdy - luy|      예)   wallpaper = [".#...", "..#..", "...#."]   S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택   드래그 한 거리 = (3 - 0) + (4 - 1) = 6을 최솟값 1 ≤ wallpaper[i]의 길이 ≤ 50모든 원소의.. 2024. 6. 28.
[프로그래머스] Lv.1 공원 산책 JAVA 풀이 문제 Lv.1 공원 산책 (방향 탐색 시뮬레이션)  :  지나다니는 길 O 장애물 X    ["방향거리", "방향거리"..]     "E 5" = 현재 위치에서 동쪽으로 5칸 이동했다는 의미     공원의 가로 길이가 W, 세로 길이가 H     공원을 나타내는 문자열 배열 park    명령이 담긴 문자열 배열 routes 3 ≤ park[i]의 길이 ≤ 50S : 시작 지점 (1개) O : 이동 가능한 통로X : 장애물1 ≤ routes의 길이 ≤ 50수행할 명령어routes의 원소는 "op n"과 같은 구조 (op는 이동할 방향, n은 이동할 칸의 수)N : 북 이동 / S : 남 이동 / W : 서 이동 / E : 동 이동1 ≤ n ≤ 9  [과정] - 2차원 배열 헷갈리지 말자!! - arr[행.. 2024. 6. 28.
[백준] 10819번 차이를 최대로 JAVA (자바) 풀이 문제 10819번 (브루트포스, 백트래킹)  :  N개의 정수로 이루어진 배열 A    배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구해라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|   [입력] :  첫째 줄에 N (3 ≤ N ≤ 8) :  둘째 줄에는 배열 A에 들어있는 정수 ( -100 ≤ 정수 ≤ 100 )   [출력] :  식의 최댓값을 출력    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  수열을 모두 바꿔가며 max 값을 찾기 때문에 브루트포스가 맞다  종료 조건) depth==N N개의 숫자를 모두 뽑았기 때문에 종료하고 sum 계산 후 result로 max값 뽑아내기  1. 계산은 i.. 2024. 6. 26.
[백준] 2529번 부등호 JAVA (자바) 풀이 문제 2529번 (백트래킹)  :  부등호 기호 ‘’가 k개 나열된 순서열 A가 있다    부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다    숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다  :  부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다    부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다   [입력] :  첫 줄에 부등호 문자의 개수 정수 k :  그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9)    [출력] :  k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함)   [과정]  탐색하자 → 브루트.. 2024. 6. 25.
[백준] 10971번 외판원 순회2 JAVA (자바) 풀이 문제 10971번 (백트래킹)  :  1번 ~ N번 도시    한 도시에서 출발해 N개의 도시를 거쳐 원래의 도시로 돌아오는 순회 여행 경로    (한 번 갔던 도시로는 다시 갈 수 없다)  :  이동 비용 W[i][j] = 도시 i에서 도시 j로 가기 위한 비용 (W[i][j] ≠ W[j][i])    W[i][i]는 항상 0 / 갈 수 없는 경우도 0  :  가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.   [입력] :  첫째 줄에 도시의 수 N (2 ≤ N ≤ 10) :  다음 N개의 줄에는 비용 행렬 (각 행렬의 성분은 1,000,000 이하의 양의 정수)    (갈 수 없는 경우는 0) [출력] :  순회에 필요한 최소 비용을 출력    [과정]  탐색하자 .. 2024. 6. 22.
[백준] 2589번 보물 JAVA (자바) 풀이 문제 2589(BFS)  :  보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시    이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다    보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라    같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다  예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간  [입력] :  첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 ) :  다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이)   [출력] :  보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기co.. 2024. 6. 21.
[백준] 1697번 숨바꼭질 JAVA (자바) 풀이 문제 1697(BFS)  :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다  :  수빈이는 걷거나 순간이동을 할 수 있다     현위치가 X일 때     걷기 = 1초 후에 X-1 or X+1    순간이동 = 1초 후에 2*X  :  동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램  [입력] :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K   [출력] :  동생을 찾는 가장 빠른 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천 2. for문 상하좌우 이동을 떠올릴.. 2024. 6. 20.
[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 JAVA (자바) 풀이 문제 24444번 (bfs) :  N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)    정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다    정점 R에서 시작하여 노드의 방문 순서를 출력하자    인접 정점은 오름차순으로 방문한다bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v]    [입력] :  첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N) :  다음 M개 줄에 간선 정보 u v (가중치 1인 양방향 간선) (1 ≤ u  ≤ N, u ≠ v)    .. 2024. 6. 20.
[백준] 11060번 점프 점프 JAVA (자바) 풀이 문제 11060번 (bfs) :  1×N 크기의 미로 ( 1×1 크기의 칸으로 이루어져 있다)    i번째 칸에 쓰여 있는 수를 Ai  :  Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프가능    (예 : 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프가능)  :  현위치 = 미로의 가장 왼쪽 끝 / 가장 오른쪽 끝으로 가려고 할 때 최소 몇 번 점프를 해야하는지 구해라    (가장 오른쪽 끝으로 갈 수 없다면 -1을 출력)   [입력] :  첫째 줄에 N(1 ≤ N ≤ 1,000) :  둘째 줄에 Ai (0 ≤ Ai ≤ 100)  [출력] :  최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력     (갈 수 없다면 -1 출력) [설명] 1. 출.. 2024. 6. 19.
[백준] 14940번 쉬운 최단거리 JAVA (자바) 풀이 문제 14940번 (bfs) :  모든 지점에 대해서 목표지점까지의 거리를 구해라    :  가로와 세로로만 움직일 수 있다   [입력] :  첫째줄에 지도 세로 n, 가로 m ( 2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000 ) :  다음 n개의 줄에 m개의 숫자 ( 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점)  [출력] :  각 지점에서 목표지점까지의 거리를 출력     (원래 갈 수 없는 땅인 위치는 0 / 목표까지 도달할 수 없는 위치는 -1 출력) [설명] 1. 시작지점을 목표지점으로 잡기각 노드에서 목표지점으로 가는 것을 계산하려면 복잡목표지점부터 시작하면 가는 노드마다 거리가 기록됨 (간편) 2. 출력은 3가지값이 0이거나 2인 지점은 애초에 움직일 수 없기 때문에 0 .. 2024. 6. 18.

티스토리툴바