알고리즘 문제 풀기

[백준] 2660 회장찾기 (java)

1. 링크- https://www.acmicpc.net/problem/26602. 풀이키워드: 플로이드 와샬 24. 플로이드 와샬(Floyd Warshall) 알고리즘  지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나...blog.naver.com - 플로이드 와샬 알고리즘을 이용한다.- 모든 정점 사이의 최단 거리를 구한다.- 구한 최단 거리 중 큰 점수를 구한다.- 큰 점수 중에서 가장 작은 점수(회장이 될 자격이있는) 를 구한 뒤 후보가 몇명이고 몇번째 인덱스가 후보인지를 출력한다.3. 소스코드- 좀 지저분하게 풀었지만.. 맞았다.import java.io.BufferedReader;import java.io.BufferedWriter;import..

[백준] 1389 케빈 베이컨의 6단계 법칙 (java)

1. 링크https://www.acmicpc.net/problem/1389 2. 풀이키워드: 플로이드 와샬 24. 플로이드 와샬(Floyd Warshall) 알고리즘  지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나...blog.naver.com - 플로이드 와샬 알고리즘을 이용한다.- 모든 정점 사이의 최단 거리를 구한다.- 구한 최단 거리를 합하고 그 합이 가장 작은 인덱스를 정답으로 출력한다.풀이 순서1. NxN 의 2차원 배열을 생성한다.2. 2차원 배열의 모든 값을 INF 로 초기화한다.   - 최단 거리를 구해야하기 때문에 기준이 되는 값을 최대값 (MAX) 로 세팅한다.INF = 987654321;3. i=j 인 값은 (열,행이 같은 인덱스..

[백준] 11403 경로찾기 (java)

1. 링크- https://www.acmicpc.net/problem/11403 2. 풀이플로이드 와샬 알고리즘을 이용해서 푼다. 단순히 거쳐가는 정점을 반복문 젤 앞에 둔다.2차원 배열이므로 2차원 배열 반복문을 돌리면서 거쳐가는 정점을 모두 확인한다.해당 문제에서는 단순히 양수인 간선 (1) 을 확인하기 때문에 [i~k] [k~j] 가 모두 1이라면 arr[i][j] 도 업데이트한다.3. 소스코드 (java)/** * https://www.acmicpc.net/problem/11403 */public class BG_경로찾기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..

[프로그래머스 level 03] - n으로 표현 (c++)

문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 Nnumberreturn 5 12 ..

[프로그래머스-Level 03] - 2xN타일링 (C++)

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 입출력 예 nresult 4 5 입..

[프로그래머스-Level 03] - 추석 트래픽(c++)

문제 설명 추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:s..