백준133 [백준 6549] 히스토그램에서 가장 큰 직사각형 / 자바 / 스택 #문제 레벨: P5알고리즘: 스택풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/6549#문제 풀이 이 문제는 스택문제이다. 여담으로 지금까지 푼 건물에 관한 문제는 스택이었다 크크. 스택에 넣고 빼는 규칙은 간단하다. 현재 건물이 Stack의 최상단보다 크면 Stack에 집어넣고 Stack의 최상단보다 작으면 현재건물보다 작은 것들을 다 빼서 넓이를 구한다. 그중 가장 큰 것이 정답이다. 빨간색 숫자는 높이를 의미한다. 높이가 2인 건물을 만나면 [1,4,5]가 담긴 숫자들을 빼며 넓이를 업데이트 한다. 일단 5x1= 5를 answer = Math.max(5,Long.MIN_Value)가 되고 2보다 4가 크니 4x2=8를 answ.. 2024. 8. 10. [백준 1700] 멀티탭 스케줄링 / 자바 / 그리드 #문제 레벨: G1알고리즘: 그리드 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1700#문제 풀이 이 문제는 순서대로 조건에 맞게 하나 씩 콘센트를 빼고 꽂는다 하여 그리드 문제이다. 그리드는 지금까지 탐색한 것들을 토대로 풀어나간다 라는 생각이 있어서 이 방식도 그리드인줄 몰랐다. 그래서 이 방식이 뭐냐? 꽂을려는 콘센트가 이미 꽂혀있는 경우는 skip하고 구멍이 넉넉한 경우에도 꽂아주고 skip한다. 신경써줘야 할 부분은 구멍이 다 꽂혀있을 경우인데 콘센트를 뽑을지는 가장 뒤늦게 다시 나오는 콘센트를 뽑는 거다. 그러기 위해서는 앞이 아닌 뒤를 탐색해야 한다. 이번 문제를 통해서 그리드 개념을 다시 세웠다. 현재까지 탐색한 것을 .. 2024. 8. 10. [백준 11401] 이항 계수3 / 자바 / 수학(파스칼 + 모듈러) #문제 레벨: G1알고리즘: 수학(파스칼 + 모듈러풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/11401#문제 풀이 이항 개수란 N개에서 순서상관없이 K개를 뽑는 것을 말한다. 보다시피 조합문제는 파스칼 문제로 치환된다. 그런데 N의 숫자가 상당하다 이정도의 파스칼을 구했다가는 어떠한 변수에도 담을 수 없다.(알고리즘 문제를 풀 때 12팩토리얼과 20팩토리얼은 각각 int와 long형이 넘어간다는 것을 알면 좋다.) 그래서 우리는 이 문제를 풀기위해서 크게 두가지를 구현해야 한다. 1. 파스칼 수 구하는 법2. 모듈러 연산(변수에 담기 위해) 1. 파스칼 수 구하는 법//일반 파스칼main { print(factorial.. 2024. 8. 9. [백준 1016] 제곱 ㄴㄴ 수 / 자바 / 수학(에라토스테네스의 체) #문제 레벨: G1알고리즘: 수학(에라토스테네스의 체)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1016 #문제 풀이 에라토스테네스의 체 문제를 한 번이라도 풀어본 사람이라면 이 문제를 보자마자 그 문제라는 것을 직감할 것이다. 다른 방식으로 찾게 된다면, 시간복잡도에서 걸리기 때문입니다. 체에서 알 수 있듯이 에라토스테네스의 체는 제한 숫자내에서 2,3,...의 제곱들을 미리 걸러주는 것는 것입니다. 만약 4의 차례가 왔다면 앞서 2의 제곱으로 이미 걸러졌기 때문에 4는 탐색을 안 하고 패스되는 것입니다.이 문제는 소수를 찾는 것이 아니고 어떤 숫자의 제곱으로 나눠지나 안 나눠지나 판단하는 에라토스테네스체의 응용문제입니다.#풀.. 2024. 8. 8. [백준 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. 이전 1 2 3 4 5 6 7 8 ··· 15 다음
