개발하는 고라니

코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr [Minimum Spanning Tree(MST), Kruskal 사용] 시작 정점, 도착 정점, 가중치 이렇게 3개의 멤버변수를 갖는 클래스 Edge를 선언하고 sort()를 이용하기 위해 Comparable 인터페이스를 구현한다. static class Edge implements Comparable{ int h, tg, d; public Edge(int home, int target, int dist){ h=home; tg=target; d=dist; } @Override public int compareTo(Edge o) { return d-o.d; }..

파일에서 문자열 데이터를 읽어 문자열 배열에다 저장하는 프로그램을 생각해보자. names.txt라는 파일에 다음과 같이 값이 있다. 강호동 유재석 하하 김지호 김현준 김태희 박민정 names.txt에서 데이터를 읽어들이기 위해 FileInputStream을 열어야 하고, 데이터를 받아오기 위해 Scanner를 생성해주자. String url = "names.txt"; String[] names = new String[10]; InputStream fis = new FileInputStream(url); Scanner sc = new Scanner(fis); 근데 문제가 있다. 파일의 입력을 계속 받아오긴 할텐데... 파일의 끝을 만나면 그만 읽어야할텐데, 그 끝을 어떻게 표현하지? Scanner를 이용한..

정수형 1차원 배열 arr을 인자로 받아 정수형 1차원 배열을 반환하는 메서드 shuffle이다. 이 메서드는 인자로 받은 배열을 무작위로 섞어준다. 보통 셔플을 하면 원소가 중복되지 않게하기 위해 부가적인 처리가 필요한 경우가 있다. 하지만 이같은 경우는 배열의 원소를 직접 다루는 것이 아닌, 배열의 인덱스를 사용해 Swap을 하므로 값의 중복이 일어날 일이 발생하지 않는다. static Integer[] shuffle(Integer[] arr) { Random ran = new Random(); Integer[] result = arr; for(int i=0; i

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [BFS] Time Limit Exceeded(TLE)를 높은 확률로 만날 수 있는 문제이다. 여러 가지 방식으로 문제를 풀어봤으나 매번 시간 초과... 결국 AC를 받은 것은 다음과 같은 방법이다. * 갈 수 있는 칸을 저장하는 int[][] move * 빈 공간에 대해 방문 체크 boolean[][] visit * 벽에 대해 방문 체크 boolean[][] wall * 지도 저장 int[][] map 1. 입력을 받으며 벽인 곳의 move..

9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net [BFS + 비트마스킹] 정말 맞왜틀? 이 질문이 여러번 나왔던 문제. 뜻밖의 반례를 찾아서 다행히 AC를 받았다. 1 6 6 .***** .A$B$* ****** .C$D$* ****** **ac** 0 answer : 2 기존 코드는 위의 반례에서 무한루프를 돌았다. 그 이유는 망각해버렸으나 어떤 열쇠를 갖고있는지에 대한 정보 (key)를 전역변수로 두어 BFS내에서 공유하게 했더니 TLE를 피했다. 그리고 "상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공..

상속이라는 단어는 아마 대부분 알 것이라고 생각된다. Java에서의 상속은 무엇일까? 자식 클래스가 상속받고 싶은 부모 클래스를 선택해서 물려받는다. 이때 상속받는 클래스 = 자식/하위/서브 클래스, 상속을 해주는 클래스 = 부모/상위/슈퍼 클래스 라고 한다. Java에서는 'extends' 키워드를 사용해 상속을 선언한다. 자식 클래스가 상속을 하게되면 부모 클래스의 필드와 메서드를 물려받는다(능력 및 기능을 제공받는다). 하지만 부모 클래스 멤버의 접근 제어자가 'private', 'default'라면 상속은 받을 수 있지만 접근은 어렵다. 그리고 자식 클래스가 여러 부모로부터 다중 상속받는 것은 불가(단일 상속)하다. 반대로 부모 클래스는 여러 자식 클래스에게 상속을 해주는 것이 가능하다. Has ..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net [BFS] 거의 브루트 포스 문제랄까.. 가능한 모든 경우의 수를 다 돌아보는 것 같다. 나는 Set과 문자열을 이용했다. 예를 들어, 1 2 3 5 6 7 8 4 0 이라는 배열이 주어진다면, String str = "123567840"; 이런식으로 문자열로 변환해 Set에 넣어 값이 중복되지 않게 (이미 방문했던 배열을 피하기 위해) 하였다. 결국 Set은 "123456780" 이라는 문자열을 넣게 될 수도, 넣지 않게 될 수도 있는데, 넣지 않게 되는 경우 '-1'을 출력하면 된다. 코딩 기술이 부족하다보니, 잡기술을 여러가지 사용한..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 모든 정점에 대하여 다른 정점으로의 최단 경로를 구하는 문제이므로 n * Djikstra / Floyd Warshall을 사용할 수 있겠다. [Dijkstra] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static class Edge implements Compa..