본문 바로가기

알고리즘

 (63)
[Java] SW Expert Academy 1824번 문제: 혁진이의 프로그램 검증 (DFS, 깊이 우선 탐색) --- 문제 --- 1824. 혁진이의 프로그램 검증 --- 코드 --- import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.io.FileInputStream; import java.io.FileNotFoundException; public class Sw1824 { // 이동 방향 : 우,좌,상,하 public static final int[][] directions = {{0,1},{0,-1},{-1,0},{1,0}}; // 당시의 상태를 저장하는 클래스 public static class Status{ int row; int col; int mem; int direc; Status(int ..
[Java] SW Expert Academy 1249번 문제: [S/W 문제해결 응용] 4일차 - 보급로 (BFS, 너비우선탐색) --- 문제 --- [S/W 문제해결 응용] 4일차 - 보급로 2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다. 전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다. 그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다. 전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다. 공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오. 깊이가 1이라면 복구에 드는 시간이 1이라고 ..
[Java] SW Expert Academy 2806번 문제: N-Queen(DFS, BackTracking, 백트래킹) --- 문제 --- 2806번 : N-Queen --- 코드 --- import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Sw2806 { public static int[] arr; public static int sum; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("./src/2806.txt")); Scanner sc = new Scanner(System.in); int T=sc.nextInt(); for(int test_c..
[Java] SW Expert Academy 1204번 문제: [S/W 문제해결 기본] 1일차 - 최빈수 구하기 (PriorityQueue, 우선순위큐) --- 문제 --- [S/W 문제해결 기본] 1일차 - 최빈수 구하기 핵심 알고리즘 : PriorityQueue, 우선순위큐 (Max Heap) --- 코드 --- 1. 점수 input을 받으면면, 동시에 0~100개의 배열 scores에서 해당 점수 자리에 +1을 한다. 2. +1을 한 수가 저장된 max값과 같으면 ? Max heap 즉, PriorityQueue에 해당 점수를 추가 +1을 한 수가 기존 max보다 크면? 기존 PriorityQueue의 값을 모두 지우고 해당 점수를 추가 3. 이 과정을 반복하고 점수를 다 받으면 PriorityQueue에서 제일 첫 우선순위 값을 출력 (저장된 수 중에서 가장 큰 값) (단, 최빈수가 여러 개 일 때에는 가장 큰 점수를 출력하라). 라는 조건이 있기..
[Java] LeetCode 문제 풀이 : Problem1 Two Sum (Array) ---문제--- Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. interger 로 구성된 배열 nums 와 interger 숫자 target 이 주어졌을 때, nums 에 포함된 숫자들 중 더해서 target 숫자가 될 수 있는 숫자 2개의 index를 반환하는 코드를 짜시오..
[Java] Progrmmers 코딩테스트 연습 : 등굣길 (동적 계획법 Dynamic Programming, BFS,Stack) --- 문제 --- 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과 n이 모두 1인 ..
[Java] Progrmmers 코딩테스트 연습 : 크레인 인형뽑기 게임 (Stack) --- 문제 --- 게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다. 만약 같은 모양의 인형 두 ..
[Python] Progrmmers 코딩테스트 연습 : 섬 연결하기 (Greedy, Kruskal) ---문제--- 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때..
728x90
반응형

티스토리툴바