끄적끄적

100 x 100 배열에서 arr[i][j]=2인 곳을 목적지로 하는 arr[0][i]의 i를 찾는 문제이다. 같은 방향으로 나아가다가 다음 위치에 1이 아니거나 다음 위치가 인덱스를 벗어나면 방향을 바꾼다. 아래로만 향하고 오른쪽이나 왼쪽이 있으면 방향을 바꾸며 나아간다. 재귀를 통해 반복하다가 arr[i][j]=2이면 탈출한다. package day0803; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Ladder { static int [][]arr; static int ans; public st..

ArrayList를 통해 배열을 정렬하고 가장 큰수에서 1을 빼고 가장 작은수에서 1을 더한다. 재귀를 통해 지정된 횟수만큼 반복하면서 매번 sort해준다. package day0803; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Flatten { public static void main(String[] args) throws IOException { //..

방향을 저장하여 앞으로 그 방향으로 나아갈 수 있으면 방향을 바꾸고 한칸 나아가고 아닐 경우 방향만 바꿔준다. 또한 총이 나아갈 때 장애물이 없다면 장애물에 부딛칠 때까지 나아가야 하므로 while문으로 통해 반복해야한다. 나는 현재 위치를 전역변수로 저장하였고, while문에서는 현재 위치와 총의 위치를 따로 매개변수로 입력받아 처리하였다. package day0803; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BattleField { static int H, W; static int direct..

마름모 모양으로 표시된 구역만 더하는데, n의 크기에 따라서 n만큼 개수를 더했다가 1까지 작아지는 형태로 규칙성을 가진다. 따라서 한줄에 받을 개수와 시작 위치를 저장하는 배열을 만들고 해당하는 위치만 더해주었다. package day0803; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Farm { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReade..

package day0803; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2001 { static int M, N; static int Max; static int[][] arr; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int test = ..

이 문제는 처음에 브루트 포스로 접근하였는데, 시간 초과가 나서 dfs를 이용하여 해결하였다. 아직도 재귀 로직이 헷갈려서 고생했다. 관련 유형을 더 풀어볼 예정이다. void dfs(vector numbers, int sum, int target, int index) { if (index == numbers.size() -1) { if (sum+numbers[index] == target) { cnt++; } if (sum - numbers[index] == target) { cnt++; } return; } dfs(numbers, sum+numbers[index], target, index+1); dfs(numbers, sum - numbers[index], target, index+1); } 만약 ..

처음 문제를 풀었을 때는 dfs를 이용해서 풀었는데, 시간 초과가 났다 ㅜ., 질문을 보니 다익스트라로 풀어야 된다는 것을 알게 됐다. 처음 접하는 개념이라, 익숙해지려면 비슷한 유형을 더 풀어봐야 할 것 같다. 다익스트라는 최단 경로 탐색 문제로, 출발 노드를 기준으로 가까운 노드들을 방문하여, 최단 경로를 계속 갱신하는 개념이다. 유의해야할 점은 이 문제에서는 같은 경로가 여러 번일 수 있고, 1 -> 3 경로를 입력한다고 3 -> 1 경로로 사용할 수 있는 것이 아니라는 것이다. #include #include #include #include using namespace std; int N, M; int graph[1001][1001]; // 가중치 저장 2중 배열 void dijstra(int s..

이 문제는 그리디 알고리즘을 학습하기 위해 푼 문제이다. 처음 접근할 때, 꽂혀있는 멀티탭 중 이후 사용할 횟수가 가장 적은 것을 빼는 것으로 생각했는데, 그것이 아닌 가장 나중에 사용할(즉, 현재를 기준으로 사용할 시기가 가장 나중) 것을 찾아야 하는 것이었다. 정리하자면, 1. 사용 가능 구멍이 존재하면 꽂음 2. 사용할 값이 꽂혀있으면 continue 3. 값을 하나 새로 꽂아야 하는 경우 1) 꽂혀있는 값들이 언제 다시 사용하는지 체크. 1-1) 만약 더 이상 사용되지 않는 것이면 그 자리에 새로운 것을 꽂음(다른 멀티탭 확인 안 해도 됨) 1-2) 모두 이후에 사용된다면, 사용 시기가 가장 나중인 것을 찾아야 함 이를 코드로 작성하면 이렇다. #include #include #include us..