본문 바로가기
반응형

CodingTEST

[프로그래머스] 주식가격 (JAVA)
CodingTEST 2024. 2. 26. [프로그래머스] 주식가격 (JAVA) 프로그래머스 - [Level 2] 주식가격 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 반환해라. 해결 키 포인트 우선순위 큐 사용 인덱스와 가격을 가지고 있을 클래스 구현 (Node) 비교 시, 가격이 큰 것부터 우선순위를 갖도록 구현 가격이 같을 경우 인덱스가 작은 것부터 우선순위를 갖도록 구현 큐에 넣기 전 큐 확인(자신보다 큰 가격이 있을 경우 반복), 큐에 삽입 현재 가장 앞에 있는 Node의 가격이 현재 가격보다 클..
[백준 2206] 벽 부수고 이동하기(JAVA)
CodingTEST 2024. 2. 22. [백준 2206] 벽 부수고 이동하기(JAVA) 백준 2206번 문제 - 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 분석 [0,0] 부터 [N,M] 까지 이동해야한다. 이동할 때, 최단 거리를 구하여라. 0은 이동 가능 1은 벽, 이동 불가능 이동 중 한 번만 벽을 뚫을 수 있다. [0,0] 부터 [N,M] 까지 이동하지 못할 경우 -1을 반환한다. 해결 포인트 BFS 사용 벽을 뚫고 방문한 경우와 벽을 뚫지 않고 방문한 경우는 다른 방문 처리를 해야한다. visited배열을 3차원 배열로 구현 boo..
[프로그래머스] 다리를 지나는 트럭 (JAVA)
CodingTEST 2024. 2. 18. [프로그래머스] 다리를 지나는 트럭 (JAVA) 프로그래머스 - [Level 2] 다리를 지나는 트럭 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 트럭 여러 대가 강을 가로질러 가야한다. 정해진 순서대로 건너야한다. 다리의 길이와 다리가 견딜 수 있는 무게가 주어진다. 다리의 길이 만큼 트럭이 올라올 수 있다. 다리를 다 건너는데, 다리의 길이만큼의 시간이 걸린다. 다리의 길이와 다리가 견딜 수 있는 무게, 그리고 트럭 리스트가 주어졌을 때 다리를 건너는데 걸리는 최소 시간을 반환해라. 해결 키 포인트 스택/큐 사용 다리에 더 이상 트럭이 올라갈 수 없을 경우, 큐에 0 삽입 (없는 무게)..
[백준 1238] 파티(JAVA)
CodingTEST 2024. 2. 11. [백준 1238] 파티(JAVA) 백준 1238번 문제 - 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 분석 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 이 때, 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은..
[백준 11404] 플로이드(JAVA)
CodingTEST 2024. 2. 11. [백준 11404] 플로이드(JAVA) 백준 11404번 문제 - 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 분석 n(2 ≤ n ≤ 100)개의 도시가 있다. 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성 해결 포인트 플로이드–워셜 알고리즘 이용 (사실 BFS로 풀었지만 설명 읽어보니 이게 플로이드–워셜 같음) 방문처리를 위한..
[백준 9663] N-Queen(JAVA)
CodingTEST 2024. 2. 11. [백준 9663] N-Queen(JAVA) 백준 9663번 문제 - N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수 해결 포인트 퀸이 공격할 수 있는 범위 상하좌우, 대각선 칸 수 제한 없이 무제한 ! DFS 사용 가로, 세로 줄은 단순하게 퀸이 놓아졌으면 놓기 금지 - 가로,세로 확인할 수 있는 배열 구현 가로 row[N] 세로 col[N] 퀸을 놓은 곳의 가로, 세로 위치를 true로 설정 퀸 위치 x,y일 때, row[x] = true; col[y] = t..
[백준 1967] 트리의 지름(JAVA)
CodingTEST 2024. 2. 11. [백준 1967] 트리의 지름(JAVA) 백준 1967번 문제 - 트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 분석 트리(tree) 사이클이 없는 무방향 그래프이다. 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리의 지름 : 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이 트리의 지름을 출력해라. 해결 포인트 DFS 사용 DFS는 최장 값을 반환 1부터 N까지 반복하면서 모든 위치에서 시작하는 DFS를 실행 코드 import java.io.*; import java.util..
[백준 1753] 최단경로(JAVA)
CodingTEST 2024. 2. 11. [백준 1753] 최단경로(JAVA) 백준 1753번 문제 - 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 분석 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 해결 포인트 다익스트라(Dijkstra) 알고리즘 사용 Edge 클래스 구현 도착지 v 가중치 w 결과를 저장할 results 배열 구현 Edge Comparable는 가중치가 작은 순으로 정렬되도록 구현 우선순위 큐 사용 Qu..
[백준 13549] 숨바꼭질 3(JAVA)
CodingTEST 2024. 2. 11. [백준 13549] 숨바꼭질 3(JAVA) 백준 13549번 문제 - 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 분석 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다 수빈이는 걷거나 순간이동을 할 수 있다. 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 출력해라. 해..
[백준 1916] 최소비용 구하기(JAVA)
CodingTEST 2024. 2. 11. [백준 1916] 최소비용 구하기(JAVA) 백준 1916번 문제 - 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 분석 N개의 도시가 있다. 도시의 번호는 1부터 N까지이다. 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 해결 포인트 다익스트라(Dijkstra) 알고리즘 사용 버스 클래스 구현 버스 도착지 버스 비용 버스 C..
[백준 2002] 추월(JAVA)
CodingTEST 2024. 2. 11. [백준 2002] 추월(JAVA) 백준 2002번 문제 - 추월 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 문제 분석 들어가는 차량 순서와 나오는 차량 순서가 주어질 때, 추월한 차량 개수를 출력해라. 해결 포인트 해시맵 사용 들어온 차량 번호와 나오는 차량 번호를 배열로 저장 추월한 차량인 경우 맵에 저장 맵을 이용한 이유 : 맵에 해당 차량이 존재하는지 확인 시 시간 고려 들어온 차량을 확인하는 index(sIndex), 나간 차량을 확인하는 index(eIndex) 선언 현재 확인하는 들어온 차량, 나간 차량이 동일..
[백준 9465] 스티커(JAVA)
CodingTEST 2024. 2. 11. [백준 9465] 스티커(JAVA) 백준 9465번 문제 - 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 분석 하나의 스티커를 떼면 근처 (좌우상하) 스티커는 손상된다 스티커에는 점수가 있다. 어떻게 스티커를 뜯어야지 가장 높은 스티커 점수를 얻을 수 있을까? 최대 스티커 점수를 출력해라 해결 포인트 DP 사용 DP는 2차원 배열로 구현 int [][] stikers = new int[2][N]; 첫 열은 해당 스티커 점수로 고정 dp[0][0] : stikers[1][0] | dp[1][0] : stikers[1][..
반응형

티스토리툴바