알고리즘182 [백준 1300] K번째 수 / 자바 / 이분탐색 #문제 레벨: G1알고리즘: 이분탐색 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1300#문제 풀이 1 ~ N*N의 숫자들을 이분탐색하여 알아낼 것이다. 해당숫자(L포인터와 R포인트에 의한 mid)를 행의 값으로 나눠주면 그 행에서 해당숫자보다 작거나 같은 숫자의 개수가 나오는 것이다. 각행마다 이 과정을 실행하고 더한 값이 B배열의 위치값(인덱스)이다. 이렇게 나온 값이 K보다 작거나 크다면 왼쪽 포인터와 오른쪽 포인터를 조절해서 해당숫자(mid)를 다시 만든다.예시를 들어 설명하겠다.N=4이고 K=9일 때초기 범위: left = 1, right = N * N = 4 * 4 = 16이진 탐색을 시작한다:mid = (1 + .. 2024. 8. 7. [백준 2042] 구간 합 구하기 / 자바 / 자료구조(세그먼트 트리) #문제 레벨: G1알고리즘: 자료구조(세그먼트 트리) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2042#문제 풀이 문제를 처음 봤을 때 누적합을 떠올렸다. 앞서 말하지만 누적합은 정답이 아니다. 배열의 1 ~i 까지의 합을 적어 놓은 것이다. 그러면 A ~ B 까지의 합을 구할 때는 A ~ B 까지 순회하는 것이 아닌 arr[B] - arr[A]를 하면 되는 것이다. 그러나 여기서 문제인 것은 값을 바꿀 때이다. 만약 2 번째 숫자를 2 -> 5를 바꿨다면 2 번째 뒤에 있는 값들은 다 업데이트 해야 한다. 왜냐하면 1 ~ i 까지의 숫자합이기 때문에 새로 바뀐 2의 숫자로 더해줘야 하기 때문이다. 답을 출력하는 것 O(1)이.. 2024. 8. 7. [백준 14890] 경사로 / 자바 / 구현 #문제 레벨: G3알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14890 #문제 풀이 문제를 보면 알겠지만 우리가 해야할 일은 명확하다. 모든 행을 검사하고 모든 열을 검사하면 된다. 그러나 조건이 많이 붙어있어 구현하는데 까다로울 수 있다. 해야 할 일이 명확하고 구현이 까다로운 경우는 밀고나가야한다. 이것은 구현문제이기 때문이다. dfs 혹은 bfs 혹은 dp 문제 같은 경우 해야 할 일이 명확하지는 않은데 구현이 지엽적인 것 같다고 느낄 때는 아이디어를 돌아볼 필요성이 있다.#풀이 코드 import java.util.*;import java.io.*;public class Main { static i.. 2024. 8. 6. [백준 15684] 사다리 조작 / 자바 / 브루트포스 + 약간의 구현 #문제 레벨: G3알고리즘: 브루트포스 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/15684#문제 풀이 난 문제를 볼 때 이것은 규칙이 있나 없나부터 가볍게 생각한다. 딱 떠오르지 않는다면 입출력 제한을 보고 완전탐색인지 확인한다. 이 문제 같은 경우 최대 (10x30)^3 사다리 구현은 어려울 수 있지만, 굳이 이 문제에서 한가지만 뽑아서 배울 수 있다면, 브루트 포스 문제 풀이 흐름이다.다리를 놓을 조합을 뽑아놓고(dfs로 구현) 조건에 맞는대로 결과가 나오는지 시뮬레이션 돌린다. #풀이 코드 import java.util.*;import java.io.*;public class Main { static in.. 2024. 8. 4. [백준 1103] 게임 / 자바 / dfs + dp #문제 레벨: G2알고리즘: dfs + dp풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/1103#문제 풀이 dfs+dp 코드 구현은 워낙 다양하다. 그래서 자기에게 맞는 코드를 찾아야 한다. 자기가 이해하기 쉬운 코드를 짜야한다. visited배열이 언제 true,false가 되고 dp 값이 어떻게 언제 채워지는지 정확히 이해해야 한다.아래 코드는 한 번씩 이동할 때마다 dp배열에 +1씩 새긴다. 만약 dp 배열에 값이 지금 새겨넣으려는 값보다 큰 경우 그 경로에서는 탐색을 멈춘다. 왜냐하면 이미 이전에 깊이 탐색했다는 뜻으로. vsited배열은 무한루프를 탐색하기 위함이기 때문에 다른경로에 영향을 주면 안된다. 한 경로에서 .. 2024. 8. 3. [백준 2504] 괄호의 값 / 자바 / 구현(괄호) #문제 레벨: G5알고리즘: 구현(괄호)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2504#문제 풀이 괄호문제가 보면 스택문제임을 깨달아야 한다. 근데 평상시 만났던 괄호가 올바른지 검사하는 문제가 아니라 괄호의 값을 계산하는 문제이다. 바로 문제 설명하겠다.( () () ) 가장 안쪽에 있느 ()는 원래 2이다. 그런데 우린 () 앞에 (가 있었으므로 4라고 칠 거다. 그 옆에 있는 ()도 4라고 치자. 그럼 답이 8이 나오지 않은가?이게 어떻게 이렇게 될 수 있을까? 분배법칙 때문에 그렇다. ( () () ) 는 (()) (()) 와 같다. 즉, 2x(2+2) 이나 (2x2 + 2x2)는 같다. 그러니 우리.. 2024. 8. 2. [백준 17144] 미세먼지 안녕! / 자바 / 구현 #문제 레벨: G4알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/17144#문제 풀이 제목이 상쾌하여 문제에 대한 호감도가 올라갔다. 풀면서 구현 문제에 적합한 것 같아 호감도가 더 올라갔다.이문제에서 우리가 구현할 것은1. 미세먼지 확산2. 공기청정기 바람 부는 것 3 . 토탈 먼지 수 구하기이 두가지이다. 1 ~ 2번을 T초 동안 반복 후 최종적으로 3번을 통해 답을 구하면 된다. 미세먼지 확산은 기존배열을 참조하여 temp(임시)배열에 값을 추가하거나 빼주면 된다................(1)기존 배열을 수정하면 다른 미세먼지 확산을 계산할 때 영향을 미치기 때문에 일단은 temp배열에 다 계산해주고 기존 배.. 2024. 8. 2. [백준 14891] 톱니바퀴 / 자바 / 구현 + 자료구조 #문제 레벨: G5알고리즘: 구현 + 자료구조풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14891#문제 풀이 위 문제는 간단한 구현 문제이다. 회전을 하기 전 그 상태가 모든 톱니바퀴의 회전 여부를 결정하기 때문이다. 만약 처음 그상태가 아니라 톱니바퀴 하나를 돌리고 나서 다른 톱니바퀴의 회전 여부를 결정해야 했다면 이것보다는 조금 더 구현이 복잡해졌을 수 있다. 1. 해당 톱니바퀴를 기준으로 연속적으로 왼쪽 톱니바퀴들이 회전하는지 체크하고 같은 방식으로 오른쪽 톱니바퀴들이 회전하는지 체크한다.2. 회전 시켜준다. 3. 스코어를 구한다. 난 이 문제를 통해 구현연습을 한 것도 있지만 자료구조를 더 집중적으로 공부해봤다. 톱니바퀴의.. 2024. 8. 1. [백준 16724] 피리 부는 사나이 / 자바 / dfs #문제 레벨: G3알고리즘: dfs풀이시간: 40분힌트 참조 유무:https://www.acmicpc.net/problem/16724#문제 풀이 문제를 쉽게 설명하자면 "시간은 상관없이 방향에 따라 이동할 때 언젠가는 세이프존에 들어갈 수 있게 해라"이다. 문제에 나와있지는 않지만 방향에 따라 갔을 때 배열을 벗어나는 경우는 없다. 이 부분이 설명이 안 되어있는게 아쉽긴 하다. 그럼 우린 dfs를 통해 싸이클을 돌면 된다. 배열 내에 싸이클의 개수가 답인 거다.dfs+cycle 개념이 이해가 안 간다면 아래에 관련 문제 링크 참조해둘테니 연습해보면 좋을 것이다.#풀이 코드 import java.util.Scanner;public class Main { static .. 2024. 7. 31. 이전 1 ··· 3 4 5 6 7 8 9 ··· 21 다음
