개발하는 고라니

12763번: 지각하면 안 돼 1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.) www.acmicpc.net [Dijkstra + DFS] N개의 정점을 탐색하는 것에서 그래프 문제임을 유추할 수 있고, 조건이 주어지며 최소한의 값으로 목표 정점에 도착하는 것을 구하는 것에서 최단경로 문제임을 유추할 수 있다. 그저 그런 다익스트라 문제인줄 알고 여유롭게 풀었지만 85% 쯤 오답판정을 받았다. 이럴리가 없는데..하면서 몇 번을 다시 제출했지만 여전히 오답이었다. 틀린 이유에 대한 해답은 질문 게시판에서 찾을 수 있었다. 링크 : https://www.acmicpc.net/board/view/37703#post..

코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 나의 문제 접근법 주어진 문자열을 문자 배열로 변환하고, 각 문자로의 이동 회수를 구했다. 예를 들어 "JAN"이라는 문자열이 주어지면 첫번째 'A'에서 'J'로 갈 수 있는 이동횟수는 오른쪽으로 이동했을 때 9회, 왼쪽으로 이동했을 때 16회인데, 이 둘 중 최소값인 9를 택한다. 마찬가지로 두번째 문자에 대해서도 동일한 방법으로 이동회수를 구한다. 현재 문자에서 왼쪽과 오른쪽으로 탐색을 하는데, 이 때 'A'가 아닌 문자가 있는 곳을 찾는..

이미지 파일을 서버에 업로드 하기전에 클라이언트 단에서 먼저 이미지를 미리보기 하고 올리고 싶을 경우가 있다. 이전에는 몇 가지 복잡한 방법을 사용했으나, 이제는 간단한 자바스크립트 처리로 충분히 가능하다. FileReader FileReader 객체는 웹 어플리케이션이 비동기적으로 데이터를 읽기 위해 읽을 파일을 가리키는 File 혹은 Blob 객체를 이용해 파일의 내용을 읽고 사용자의 컴퓨터에 저장하는 것을 가능하게 해준다. File 객체는 태그를 이용하여 유저가 선택한 파일들의 결과로 반환된 FileList 객체, 드래그 앤 드랍으로 반환된 DataTransfer 객체 혹은 HTMLCanvasElement의 mozGetAsFile() API로부터 얻는다. Event Handler 이미지 미리보기 먼..

코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [DFS + 백트래킹] 입력으로 들어온 문자열을 한 글자씩 쪼개어 char[] 에 저장하고, 각 인덱스에 해당하는 문자마다 방문했는지를 체크하기 위한 boolea[] visit를 준비했다. 즉 "017" 이라는 문자열이 있을 때 0은 0번째, 1은 1번째, 7은 2번째로 , 0을 포함하고 있다면 visit[0] = true가 되고, 0을 포함한 채로 1을 포함하고 있다면 visit[0]과 visit[1] 은 참이 된다. 백트래킹을 이용했기 때문에 ..

코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr [BFS] BFS의 가장 전형적인 문제. 최단거리를 구할 때 DFS를 이용하려할 수도 있는데, 이는 잘못된 것이다. DFS가 탐색하는 곳은 항상 최적해(최단거리)는 아니기 때문이다. # Code import java.util.LinkedList; import java.util.Queue; class Solution { static class Point{ int y, x, move; public Point(i..

순수 Servlet을 이용해 파일을 업로드하고 로컬 저장소에 저장하는 것을 알아보자. 먼저 서버사이드에서 파일을 업로드하는 방법은 가장 간단하게 태그를 이용한 POST 방식이 있다. (form태그 속성 중 enctype을 반드시"multipart/form-data"로 변경) 자바스크립트와 Ajax를 이용한 방법도 있지만 이는 다음에 알아보고자 한다. 먼저 form 태그에 파일과 내용을 달아보자. 제목 첨부파일 저장 취소 reg라는 URL로 제목(title), 내용(content) 그리고 파일(f)가 전송될 것이다. 이를 Controller에서 받는 방법을 소개한다. Controller에서 파일 정보 가져오기 우리는 그동안 body에 담긴 데이터든, 쿼리스트링에 붙어있는 값이든 request.getPara..

4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net [DFS] 다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다. 사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다. static boolean DFS..

18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net [BFS + 우선순위 큐] 1초마다 낮은 번호의 바이러스부터 상하좌우 인접한 칸(단, 0인 곳)으로 한 칸씩 전염시킬 수 있으므로 우선순위 큐를 사용해 낮은 번호의 바이러스부터 퍼지게 한다. 그러려면 입력을 받을 때 모든 바이러스를 우선순위 큐에 넣는다. 그리고 s번의 루프를 수행하고, 각 루프마다 BFS를 실행하는데 일반적인 BFS는 다음 탐색할 정점을 동일한 큐에 저장하는데 반해, 이 문제에서는 다른 큐(tmpQ라고 지정)에 저장..