LinkedList를 이용해서 간단하게 풀었다.


import java.io.*;
import java.util.*;
/**
* BOJ 2605 줄 세우기
* https://gist.github.com/KSH-code/5d0af23c0bd3317ce83254be13a672f9
*/
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
String str1[] = br.readLine().split(" ");
for(int i = 2; i<=N; i++){
linkedList.add(linkedList.size() - Integer.parseInt(str1[i - 1]), i);
}
for(int i = 0; i<N; i++){
bw.write(linkedList.get(i) + " ");
}
bw.flush();
}
}
view raw LinkedList.java hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 11404 플로이드 Floyd-Warshall  (0) 2017.10.18
BOJ 1717 집합의 표현 disjoint-set  (0) 2017.10.17
BOJ 1753 최단경로 다익스트라 알고리즘 (Dijkstra)  (0) 2017.10.17

다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.


다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.

그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.


플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.



입력에서 중복값 확인을 해주니 정답이 됐다.


위키백과에 JAVA코드도 추가했다.



import java.io.*;
import java.util.*;
/**
* BOJ 11404 플로이드
*/
public class Main{
private static final int MOD = (int)(1e+9)+7;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int V = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
int d[][] = new int[V + 1][V + 1];
for(int i = 1; i<=V; i++){
Arrays.fill(d[i], Integer.MAX_VALUE);
d[i][i] = 0;
}
for (int i = 0; i<E; i++){
String str1[] = br.readLine().split(" ");
int a = Integer.parseInt(str1[0]);
int b = Integer.parseInt(str1[1]);
int c = Integer.parseInt(str1[2]);
d[a][b] = Math.min(c, d[a][b]);
}
floyd(d, V);
for(int i = 1; i<=V; i++){
for(int j = 1; j<=V; j++){
bw.write(d[i][j] + " ");
}
bw.write("\n");
}
bw.flush();
}
private static void floyd(int d[][], int V){
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++) {
if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) continue;
if (d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
view raw Floyd-Warshall.java hosted with ❤ by GitHub

위키백과 JAVA

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18
BOJ 1717 집합의 표현 disjoint-set  (0) 2017.10.17
BOJ 1753 최단경로 다익스트라 알고리즘 (Dijkstra)  (0) 2017.10.17

disjoint-set 을 처음 공부했다.


서로소에 대해서 기억이 가물가물해 찾아봤는데, 서로 다른 숫자의 집합.



이 문제는 disjoint-set에 대해 기초만 알면 되는데, find, link만 알면 된다.



import java.io.*;
import java.util.*;
/**
* BOJ 1717 집합의 표현
*/
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str1[] = br.readLine().split(" ");
int n = Integer.parseInt(str1[0]), m = Integer.parseInt(str1[1]);
int disjoint[] = new int[n+1];
for(int i = 0; i<=n; i++){
disjoint[i] = i;
}
for(int i = 0; i<m; i++){
String str2[] = br.readLine().split(" ");
int a = Integer.parseInt(str2[0]), b = Integer.parseInt(str2[1]), c = Integer.parseInt(str2[2]);
if(a == 0){
// c 의 부모를 b의 부모로 한다.
link(disjoint, b, c);
}else{
// c의 부모와 b의 부모가 맞다면
if(find(disjoint, b) == find(disjoint, c))
bw.write("YES");
else
bw.write("NO");
bw.write("\n");
}
}
bw.flush();
}
/**
* 트리 구조이기 때문에 루트를 변겅하면 그 밑에것들은 알아서 따라오게 된다.
*/
private static void link(int dis[], int x, int y){
dis[find(dis, y)] = find(dis, x);
}
/**
* 트리 구조에서 루트를 찾기위해 재귀함수를 이용한다.
*/
private static int find(int dis[], int x){
if(dis[x] == x) return x;
else return dis[x] = find(dis, dis[x]);
}
}
view raw Disjoint-Set.java hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18
BOJ 11404 플로이드 Floyd-Warshall  (0) 2017.10.18
BOJ 1753 최단경로 다익스트라 알고리즘 (Dijkstra)  (0) 2017.10.17

A 집합이 있을 때,

A[i] > A[j], i < j 면 역위

저작자표시

'IT > 여러가지' 카테고리의 다른 글

JAVA parseInt valueInt 차이점  (0) 2017.11.16
ksh-code.github.io index.html 생성  (0) 2017.10.23
Typescript를 사용한 React  (0) 2017.10.22
카카오 블라인드 테스트 2차 후기  (0) 2017.10.15
카카오 블라인드 테스트 2차 준비  (0) 2017.10.13

나무위키에 올라온 사진들을 보며 코드를 작성했다.



MAX값을 2147483647 즉 signed int 의 MAX로 하다보니, 출력에서 꼬여가지고 출력초과과 떴었다.

백준의 출력 용량은 최대 1 MB이다


그 다음에 MAX값을 변경해서 제출하니 시간초과가 뜨는 것이다.

우선순위 큐로 작업하지않고, 리스트에 다 담아서 작업했었음.


그래서 큐에서 값이 변경될 경우에 offer해줬고, 성공했다.




import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
public int V,W;
public Node(int V, int W){
this.V = V; // U -> V 할때 V
this.W = W; // U -> V 의 가중치
}
@Override
public int compareTo(Node arg0) {
return this.W - arg0.W; // 오름차순 정렬
}
}
/**
* BOJ 1753 최단경로
*/
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// Node 개수와 엣지 개수를 입력받음
String str1[] = br.readLine().split(" ");
int V = Integer.parseInt(str1[0]);
int E = Integer.parseInt(str1[1]);
PriorityQueue<Node> edges[] = new PriorityQueue[V+1];
Queue<Integer> tempQueue = new LinkedList<>();
for(int i = 1; i<=V; i++)
edges[i] = new PriorityQueue<>();
// 시작 정점 입력받고, 가중치 배열 생성
int K = Integer.parseInt(br.readLine());
int W[] = new int[V+1];
Arrays.fill(W, 9898798);
W[K] = 0;
// 시작정점 담아준다.
for(int i = 0; i<E; i++){
String str2[] = br.readLine().split(" ");
int u = Integer.parseInt(str2[0]);
int v = Integer.parseInt(str2[1]);
int w = Integer.parseInt(str2[2]);
edges[u].offer(new Node(v, w));
}
tempQueue.offer(K);
while(!tempQueue.isEmpty()){
int s = tempQueue.poll(); // 시작
Iterator it = edges[s].iterator();
while(it.hasNext()){
Node tempNode = (Node) it.next();
if (W[tempNode.V] > tempNode.W + W[s]) {
tempQueue.add(tempNode.V);
}
W[tempNode.V] = Math.min(tempNode.W + W[s], W[tempNode.V]);
}
}
// 값 출력
for(int i = 1; i<=V; i++){
if(W[i] == 9898798)
bw.write("INF");
else
bw.write(String.valueOf(W[i]));
bw.write("\n");
}
bw.flush();
}
}
view raw Dijkstra.java hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 14852 타일채우기 3 풀이  (0) 2017.10.18
BOJ 2309 일곱난쟁이 풀이  (0) 2017.10.18
BOJ 2065 줄 세우기  (0) 2017.10.18
BOJ 11404 플로이드 Floyd-Warshall  (0) 2017.10.18
BOJ 1717 집합의 표현 disjoint-set  (0) 2017.10.17

REST API를 이용해서 JSON parse를 하는 문제였다.


평소 서버언어로 많이 사용하던 Node.js를 사용해서 풀었다.

근데 내 문제인지 Node.js http 모듈 문제인지 중복된 값이 들어가서 - 점수가 됐다.


내 고집으로 Node.js를 계속 사용한게 첫 번째 잘못이고,

http 모듈만을 이용해서 구현하려 했던 것이 두 번째 잘못이다.


결론 : 망함, 언어를 바꿀걸 그랬다.



내 풀이 방식은 틀리지 않았다고 한다. (올라오는 글들을 보면)

혹시 Node.js를 사용해서 성공하신 분은 tjdgnsqn133@gmail.com으로 연락해주세요. 궁금한게 많아요.


저작자표시

'IT > 여러가지' 카테고리의 다른 글

JAVA parseInt valueInt 차이점  (0) 2017.11.16
ksh-code.github.io index.html 생성  (0) 2017.10.23
Typescript를 사용한 React  (0) 2017.10.22
역위  (0) 2017.10.17
카카오 블라인드 테스트 2차 준비  (0) 2017.10.13

REST API를 이용해서 JSON들을 조작해라.


Json을 쉽게 이용하기 위해 Node.js를 사용했다.(Node는 내가 사용하던 언어)




Http Client를 구현해봤다.

http내장 모듈 사용함.

https://github.com/KSH-code/HttpClient-Nodejs

저작자표시

'IT > 여러가지' 카테고리의 다른 글

JAVA parseInt valueInt 차이점  (0) 2017.11.16
ksh-code.github.io index.html 생성  (0) 2017.10.23
Typescript를 사용한 React  (0) 2017.10.22
역위  (0) 2017.10.17
카카오 블라인드 테스트 2차 후기  (0) 2017.10.15

+ Recent posts

티스토리툴바