알고리즘 연습

송아지 구하기 문제(BFS)이동할 수 있는 거리의 경우의 수는 1, -1, 5

문제 (경로탐색, 인접행렬)총 정점수 n, 간선 수 mm개 만큼의 간선의 수가 주어짐1부터 n번까지 가는 경우의 수를 구하여라인접행렬의 단점n의 수가 10000개 이상으로 가면graph 10001을 지정해야하므로 메모리에 매우 비효율적이다.또한 인접행렬을 구하기 위해서

문제 (경로탐색, 인접리스트)총 정점수 n, 간선 수 mm개 만큼의 간선의 수가 주어짐1부터 n번까지 가는 경우의 수를 구하여라인접행렬의 단점보완1에서 2,3,4가 인접되어 있으면1 -> 2, 3, 4를 리스트로2에서 1,3이 인접되어 있으면2 -> 1, 3을 리스트로

그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 구하라풀이 1) 트리로 구하기풀이 2) distn로 만들어 구하기입력)n(정점수), m(간선수).. 인접 정보6 91 31 42 12 53 44 54 66 26 5출력)2 : 33 : 14 : 15 : 26

계단의 수 N이 주어지고 한번에 한계단 혹은 두계단씩 오를수 있다.N 계단을 오를 수 있는 경우의 수?

N개의 돌로만든 다리한번에 한칸 또는 두칸씩 건널 수 있다.

조합의 경우수(메모이제이션)nCr = n-1Cr-1 + n-1Cr 을 통하여 조합의 수를 구하라

최대점수 구하기 (DFS)N개의 문제얻는 점수와 푸는데 걸리는 시간제한시간 M안에 N개의 문제 중 최대 점수N, M// 점수와 시간ex)5 2010 525 1215 86 37 4

거스름돈이 가장 적은 동전동전의 개수 N개두번 째 줄에는 N개의 동전의 종류거슬러줄 금액 Mex)31 2 515

조합의 경우의 수를 구하여라(메모이제이션)nCr = n-1Cr-1 + n-1Cr첫째 줄에 자연수 n r이 주어지고 조합의 수를 구하여라ex)5 3출력10

미로탐색 (DFS)7 \* 7 격자판 미로를 탈출하는 경로의 수(1,1)에서 출발, 도착점은 (7,7)1은 벽이고 0은 통로이다.상하좌우로 움직일 수 있다.입력)0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 0

미로탐색 (BFS)7 \* 7 격자판 미로를 탈출하는 최단경로(1,1)에서 출발, 도착점은 (7,7)1은 벽이고 0은 통로이다.상하좌우로 움직일 수 있다.입력)0 0 0 0 0 0 00 1 1 1 1 1 00 0 0 1 0 0 01 1 0 1 0 1 11 1 0 0 0

며칠이 지나면 토마토들이 모두 익는지 최소 일수를 구하라1은 익은 토마토,0은 익지 않은 토마토\-1은 토마토가 없음하나의 인접한 토마토가 상하좌우 네 방향의 토마토에 영향을 준다.하루 지나면 주변의 토마토가 익게 된다.출력토마토가 모두 익을때까지 최소 날짜 출력저장될

N명이 지원하였고A라는 지원자가 다른 모든 지원자보다 키와 몸무게가 모두 낮으면 선발에서 탈락된다.ex)5172 67183 65180 70170 72181 60(183, 65), (180, 70), (170, 72) 가 선발됩니다.(181, 60)은 (183, 65)보

회의실 시간표n개의 회의들에 대하여 각 시작시간, 끝나는 시간이 주어져 있고회의가 겹치지 않게 회의할 수 있는 최대 수를 찾아라ex)51 42 33 54 65 7출력 : 3ex)33 31 32 3출력 : 2

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인피로연장에 동시에 존재하는 최대 인원ex)514

최대 수입 스케쥴(PriorityQueue 응용문제)N개의 기업에서 강연 요청이 왔다.D일안에 와서 강연하면 M만큼의 강연료를 받는다.D와 M만으로 가장 많이 받을 수 있는 금액을 추출하라ex)650 220 140 260 330 330 1출력 : 150

다익스트라 알고리즘가중 방향의 그래프에서 1번 정점에서 모든 정점으로의 최소 거리 비용을 출력하는 프로그램을 작성하라(경로가 없으면 Impossible을 출력하라)정점의 수 N, 간선의 수 M이 주어진다.그 다음 M 줄에 걸쳐 연결정보와 거리비용이 주어진다.출력) 1번

N\*N 섬나라 아일랜드에서 몇개의 섬이 있는지 구하라각 섬은 1로 표시되어있고 상하좌우와 대각선으로 연결되어 있고 0은 바다이다.섬나라 아일랜드에 몇개의 섬이 있는지 구하라.입력)71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0

N\*N 섬나라 아일래느에서 몇개의 섬이 있는지 구하라각 섬은 1로 표시되어있고 상하좌우와 대각선으로 연결되어 있고 0은 바다이다.섬나라 아일랜드에 몇개의 섬이 있는지 구하라.입력)71 1 0 0 0 1 00 1 1 0 1 1 00 1 0 0 0 0 00 0 0 1 0

N, M을 입력했을떄nCm을 출력하라ex) 6 4출력)0 1 2 30 1 2 40 1 2 50 1 3 40 1 3 50 1 4 50 2 3 40 2 3 50 2 4 50 3 4 51 2 3 41 2 3 51 2 4 51 3 4 52 3 4 5

0은 빈칸, 1은 집, 2는 피자집집과 피자집의 거리는 |x1-x2| + |y1-y2|이다M개의 피자집을남긴다고할때피자배달거리가 최소가 되는 M개의 피자 배달거리를 구하라NXN의 도시지도, M개의 피자집ex)4 40 1 2 01 0 2 10 2 1 22 0 1 2출력)

가장높은 탑의 높이를 구하라.탑을 쌓을때 밑면이 좁은 벽돌위에 넓은 벽돌을 쌓을 수 없다.무게가 무거운 벽돌위에 가벼운 벽돌을 놓을 수 있다.입력)첫째줄 : 입력될 벽돌의 수둘째줄부터 : 밑면의 넓이, 벽돌의 높이, 무게가 차례대로 주어진다.ex)525 3 44 4 6

거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게주면되는가입력)첫째 줄에 동전의 종류개수 N두번째 줄에는 N개 동전의 종류마지막 줄에 거슬러줄 금액 Mex)31 2 515출력) 거슬러줄 동전의 최소의 개수를 출력3

N개의 문제를 풀수 있다.제한 시간 M에서 얻을 수 있는 최대점수를 구하라.첫번째 줄에 N과 M입력두번째줄 부터 문제 풀었을때 얻는 점수와 시간ex)5 2010 525 1215 86 37 4출력) 최대점수41

N개 원소를 가진 자연수 집합두개의 부분집합으로 나누었을때, 두 부분집합의 합 서로 같은 경우에는 YES 아닌 경우엔 NOex){1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재입력

창고의 토마토가 익은것도 있고(1) 안익은것도 있고(0) 토마토가 없는 곳(-1)도 있다.며칠이 지나야 토마토가 다 익을 수 있는가?걸리는 최소날짜를 출력하고 다 못익는 상황이면 -1을 출력입력)6 40 0 -1 0 0 00 0 1 0 -1 00 0 -1 0 0 00

N개의 자연수로 이루어진 수열에서 작은수에서 가장 큰수로 증가하는 원소들의 집합 중에서 가장 큰 길이를 찾아라ex)원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12이고문제의 답은 5이다

프로그래머스 159994https://school.programmers.co.kr/learn/courses/30/lessons/159994?language=java코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는

프로그래머스 159993https://school.programmers.co.kr/learn/courses/30/lessons/1599931 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있

대충 만든 자판.txthttps://school.programmers.co.kr/learn/courses/30/lessons/160586

Q2. 몫구하기https://school.programmers.co.kr/learn/courses/30/lessons/120805class Solution { public int solution(int num1, int num2) { retu

프로그래머스 추억 점수https://school.programmers.co.kr/learn/courses/30/lessons/176963