알고리즘 문제 풀기

[백준] 2056 작업 (java)

1. 문제https://www.acmicpc.net/problem/20562. 풀이키워드: 위상정렬(위상 정렬에 대해서는 이 블로그를 참고하자) - 위상정렬의 핵심은 아래 네가지 변수를 잘 선언하는 것이다. (위 블로그 참조)- 이 문제에서는 같은 순서(같은 선행조건을 가진)의 작업이라면 동시에 실행된다고 했다. 또 모든 작업을 완료 해야하기 때문에 동시에 실행되는 작업에서는 결국 가장 오래 수행되어야 하는 작업의 시간을 더해야한다. 3. 소스코드package org.hanghae;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import..

[백준] 2179 비슷한 단어 (java)

1. 문제https://www.acmicpc.net/problem/21792. 풀이키워드- 구현풀이- 문자열들을 배열에 담고 반복문 2개를 돌려가면서 서로 매칭되는 단어의 최대 수를 구한다.- 최대 수에 해당하는 단어들의 인덱스를 저장하고 출력한다.3. 소스코드package org.hanghae;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class BG_비슷한단어 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream..

[백준] 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 ..