목록분류 전체보기 (42)
끄적끄적
마름모 모양으로 표시된 구역만 더하는데, 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 = ..
싸피 6기 합격
졸업하고 취준 기간이 길어지던 중 부족한 부분이 많다고 느껴 싸피에 지원하게 되었다. 우리학과 선배들도 꽤 많이 했던걸로 알고있고 정말 좋은 기회라 생각하여 도전하게 되었다. 1지망엔 되지 못해 아쉬운 부분이 있지만 아마 최소 1학기는 비대면일 것같고 붙은것 만으로도 너무 감사하기에 정말 열심히 해볼 생각이다!! 아자,,!
이 문제는 처음에 브루트 포스로 접근하였는데, 시간 초과가 나서 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..
백준 1700 멀티탭 스케줄링
이 문제는 그리디 알고리즘을 학습하기 위해 푼 문제이다. 처음 접근할 때, 꽂혀있는 멀티탭 중 이후 사용할 횟수가 가장 적은 것을 빼는 것으로 생각했는데, 그것이 아닌 가장 나중에 사용할(즉, 현재를 기준으로 사용할 시기가 가장 나중) 것을 찾아야 하는 것이었다. 정리하자면, 1. 사용 가능 구멍이 존재하면 꽂음 2. 사용할 값이 꽂혀있으면 continue 3. 값을 하나 새로 꽂아야 하는 경우 1) 꽂혀있는 값들이 언제 다시 사용하는지 체크. 1-1) 만약 더 이상 사용되지 않는 것이면 그 자리에 새로운 것을 꽂음(다른 멀티탭 확인 안 해도 됨) 1-2) 모두 이후에 사용된다면, 사용 시기가 가장 나중인 것을 찾아야 함 이를 코드로 작성하면 이렇다. #include #include #include us..
백준 14719 - 빗물(C++)
처음 이 문제를 풀 때는 물 웅덩이가 생기는 부분이 작은 단위로 쪼개서 생각해야한다고 잘못 접근하였다. 그러다 그릇처럼 생각해보았을 때 양끝의 높이의 최저와 내 위치에서의 높이의 차가 웅덩이 깊이가 된다는 것을 알았다. 즉, 내 위치 기준으로 왼쪽으로 최고 높이, 오른쪽으로 최고 높이를 찾고, 더 낮은 최고 높이와 나의 높이를 빼는 것이다. 위 그림을 보면 분홍색이 현재 위치일 때, 왼쪽 노랑 블록이 왼쪽 최고 높이, 오른쪽 노랑 블록이 오른쪽 최고 높이가 된다. 왼쪽 노랑 블록이 더 작으므로 분홍 블록에서의 웅덩이 높이는 [왼쪽 블록 높이 - 분홍 블록 높이]이 된다. int high, width; cin >> high >> width; int arr[501] = { -1, }; int left = 0..