SK_MOUSE 개발일기

https://www.acmicpc.net/problem/17779 dfs문제인것처럼 보였으나 완전탐색으로 구현하는 문제였다. 경계값 비교 및 break문을 이용하기 위해 역방향으로 탐색하는 방식이 필요했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int N; static int[][] grid; static int totalPeople = 0; static int min = Integer.MAX_VALUE; public static void main(String[] args)..

단순 구현문제이다. 소요시간(약 2시간50분) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, K; static Smell[][] grid; static Shark[] sharks; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine())..

가로 세로 길이 있는지 판별하는 문제 => 구현문제였다. 가로, 세로 배열에 대하여 1차원배열로 추출해서 앞뒤연산을 구현하는 문제이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] map; static int n; static int l; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..

이 문제는 두가지 방식으로 풀이할수있는데, 플로이드워셜이 직관적으로 잘 와닿아서 먼저 소개하겠다. 그리고 다익스트라 알고리즘으로 풀이를 살펴보겠다. 플로이드 워셜 알고리즘 : 최단경로 업데이트하면서 진행 모든 노드에서 다른 모든 노드까지의 최단 경로 다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정 필요x ->다익스트라와 차이점 2차원 테이블에 최단 거리 정보 저장 DP에 속함 (2차원 테이블의 값을 점화식에 따라 처리하므로 dp임) 각 단계마다 특정 노드 K 거쳐 가는 경우 확인 A -> B로 가는 최단 거리보다 A에서 K를 거쳐 B로 가는 거리가 더 짧은지 Dab = min(Dab, Dak+ Dkb)..

경계값 넘어설떄 오버플로우/언더플로우값 처리 방법은 아래 링크참고 https://skmouse.tistory.com/entry/JAVA-%EB%B0%B1%EC%A4%80-%EB%A7%88%EB%B2%95%EC%82%AC-%EC%83%81%EC%96%B4%EC%99%80-%ED%8C%8C%EC%9D%B4%EC%96%B4%EB%B3%BC [JAVA] 백준 마법사 상어와 파이어볼 이틀만에 성공했다... grid는 x,y를 row col을 이처럼 적용해야된다. 보통 (r,c)로 주어지니 (y,x)로 받아야한다!! 우선 아래 코드에서는 x,y값을 반대로 적용했다. 그래서 문제 푸는내내 계속 헷갈렸다. skmouse.tistory.com 구현문제였다. (소요시간 : 2시간) 단순 구현문제였는데, N값의 경계값을 넘..

DFS를 이용한 문제이다. 처음에는 사다리타기의 경우의 수를 구하는것이 너무 많다고 생각했는데, 문제에서 다리를 3개보다 많이 추가해야되는 경우는 -1로 출력하라는 조건이 더해져서 효율성에 대한 부담을 덜었다. 1. main문에서 추가하는 다리의 개수를 0,1,2,3개에 대하여 dfs를 각각 시도한다. 그 이상의 경우는 출력을 -1로 통일한다. 2. 사다리를 추가하는것은 dfs메소드로 추가한 다음, 해당 경우가 i번째 는 i번째에 도착하는지 check메소드로 확인한다. 3. 만약 check 메소드로 위 조건이 일치한다면 true를 반환하여 종료시킨다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

문제를 통해 배울점은 두가지였다. 1. 구간합 : 투 포인터 알고리즘(Deque와 같음) 2. 누적합의 최적화 1. 구간합 : 투 포인터 알고리즘(Deque와 같음) 먼저 일정한 길이의 구간을 계속해서 더해야 될때의 투포인터 알고리즘을 설명해보겠다. 아래와 같이 구간의 길이가 3이락 할때, 구간의 합이 최대인 구간을 구하려고 한다. => 전에 구한 구간합에서 가장 첫 원소를 빼고 다음 원소 하나를 더해주면 다음 구간합과 같다. 위 알고리즘을 적용한코드는 아래와 같다. //Deque처럼 이전값의 맨앞값 빼고 새로운값 더하기 for(int i=advTime; imax){//최대값 비교 max=sum; maxStartTime=i-advTime+1; } before=sum; } 2. 누적합의 최적화 누적합의 최..

단순 구현문제인줄 알았는데, 연결리스트를 통한 구현이어서 어려웠다. 노드는 아래 그림과 같이 순서대로 연결한다. 1. 직선방향으로 시작~도착까지 Node.next(연결된 객체1)로 연결 2. 지름길 같은경우는 addNext를 통해 10,20,30에 해당하는 노드를 찾아서 Node.fastPath(연결되 객체2)에 연결해준다. 3. permutation을 통해서 order[] 배열에 순열 경우의수를 dfs로 탐색한다. 4. dfs로 깊이 10까지 채웠으면, 해당 order[]배열을 통해 order[i]번째에 해당하는 Node[] horse에 넣어주는 gamestart를 시행한다. 5. 한가지 order경우의 수에 대해 gamestart를 완료했으면, Max값과 방문한 노드값들의 합(gamestart메소드 ..

2 20 50 50 30 20 40 헛점으로 기록된 부분은 오른쪽/아래로 탐색하는데 유턴해서 돌아오는경우(아래 예시) (0,1) (0,2) ↓ ↑ (1,1)→ (1,2) right값이나 down값으로 dfs를 엮을수 없다. 따라서 현재 좌표 위치에서 1. 왼쪽좌표의 right값이 true인지 2. 위의좌표의 down값이 true인지 를 통해서 추가로 확인해줌으로써 국경들을 모두 이을 수 있었다. 전체코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringT..

구현문제이다. 생각보다 구현에있어서 많은 시간이 든 문제이다. 실버 1문제인데 체감은 골드5정도 되는 느낌이다. 구현 방식대로 one,two,three는 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. 위 사항을 그대로 구현한 것이다. 단, 구현하면서 인접한 칸에 좋아하는사람이 있는지 확인할때는 contains메소드를 통해서 Set(좋아하는 사람 모음)에 해당 num(좋아하는사람)이 있는지 존재여부만 확인한다. contains를 생..