개발하는 고라니

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net [BFS] 4가지의 함수를 구현하기만 하면 간단한 BFS이다. 이 문제의 핵심은 L()과 R()에서 얼마나 시간을 단축하느냐에 달린 것 같다. L, R 함수는 언뜻보면 간단하지만, 항상 4자리임을 가정하고 하는 것이라, 4자리 이하일 때 "0"을 채워 4자리를 만들어줘야한다. 이 과정이 노련한 사람에게는 짧고 간편한 코드로 작성할 수 있겠으나... 나같은 초심자에게는 잡기술을 동원해서 겨우 AC를 받아내었다. static int L(int x){ S..

10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [해싱 + 이진 탐색 (Hashing + Binary Search)] 해싱없이 이진 탐색만으로 값을 검색하면 온전히 모든 값을 다 돌지 못한다. 예를 들어 10이 몇 개 있는지 검색을 할 때 10이 3개 있다고 가정한다면 3개를 모두 돌지 못할 수 있다. 따라서 해싱을 이용해 배열에 해당 값이 몇 개가 있는지 저장해놓으면 편리하다. 나는 다음과 같은 해싱을 사용하였다. 값의 범위는 (-10,000,000 ~ 10,000,000)이..

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [이분 탐색] 이분 탐색 문제를 풀며 느끼는 거지만, int 보다는 long을 쓰는게 비교적 안전할 것 같다. 세심히 주의를 기울인다면 int를 사용했을 때 overflow가 나오는 것을 캐치할 수 있으나, 작은 수들을 다루다 보면 이를 무심코 지나칠 수 있는 것 같다. 이 문제의 핵심은 (1) left = 1, right = 갖고있는 랜선의 최대 길이 (2) int는 overflow가 발생하므로 long을 사용 (3) N개의 랜선을..

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [이진 탐색, Binary Search] 그래프 문제를 주로 풀다가 문제의 스펙트럼을 좀 넓혀보고자 이진 탐색 문제를 풀기로 하였다. 이진 탐색의 기본적인 내용을 다루며 응용에 힘쓰도록 한다. 이 문제는 교과서적인 이진 탐색을 물어보는 문제이고, m개의 데이터에 대해 이진 탐색을 수행하면 되므로 딱히 어려울 것은 없어보인다. # Code import java.io.BufferedReader; import java.io.IOExcept..

1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net [BFS] 4자리 이면서 소수인 숫자를 한 자리씩 바꾸는데, 바꿔서 완성된 4자리 수도 소수이어야 한다. 그래서 목표 소수까지 가야하는데, 한 자리씩 어떻게 바꿀 것 인가에 대한 방법은 다양할 것이다. 나는 문자열로 변환하여 풀었다. 예를 들어 1033이라는 수가 있으면, 이를 문자열로 변환하고 1000의 자리, 100의 자리, 10의 자리, 1의 자리에 각각 0~9를 대입하며 (1) 방문했었는지 ? (2) 4자리 숫자인지 ? (3) 소수인지 ? 를 따져서 해당 조건을 ..

코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr [Kruskal 알고리즘] 입력으로 들어오는 land[ ][ ]의 각 원소에 인덱스를 부여했다. 이차원 배열에서 인덱스를 부여하는 방법은 (i * N) + j 이다. 이렇게 하면 0부터 N-1 * N-1까지 원소에 대해 인덱스를 부여할 수 있다. 이는 곧 정점을 정의할 수 있다는 것이므로 크루스칼 알고리즘을 수행하기에 더욱 수월해진다. 우선 이중 for문을 돌며 land의 각 원소에 대해 상..

코딩테스트 연습 - 섬 연결하기 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를 이용한..