본문 바로가기

백준133

[백준 17070] 파이프 옮기기1 / 자바 / dp #문제         레벨: G5알고리즘: dp 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17070#문제 설명    문제에서 놓칠 수도 있는 부분 몇 가지만 짚고 넘어가겠습니다.1. 파이프는 90~180도까지 +45도 or -45만 움직일 수 있다.2. 대각선 파이프는 4칸을 차지한다. 그 4칸 중 벽(1)이 있으면 안 된다. 이 문제는 dfs 또는 dp로 풀 수 있습니다. dfs로 풀 수 있는 이유는 입력최대값이 작아서 그렇습니다. 저는 dp를 공부중이기 때문에 dp를 사용해서 풀겠습니다. #알고리즘 설명   dp를 알려면 이 유형은 꼭 알아두었으면 좋겠습니다. 이 문제에서 어떻게 dp를 이용하냐면, 각 위치에 도착할 수 있는 경우의 수를 담는 것입니.. 2024. 7. 10.
dp 뿌시기 1(feat 양치기) 이 글은 고급 알고리즘인 dp의 이해를 위해 작성하였습니다. 다른 알고리즘 같은 경우 설명과 코드를 보면 이해가 단 번에 이해가 갔지만, dp의 경우에는 일반적 사고와는 달라 이해하기 쉽지 않았습니다. 이를 위해 dp의 다양한 유형을 분석하므로써 dp의 사고흐름을 정확히 이해하기 위해 작성하였습니다. 아래 문제들은 백준 골드 정도 되는 문제들로 구성되어있습니다. 문제풀이에서 가장 중요한 건 어떤 알고리즘인지 파악하는 게 중요하기 때문에 dp문제라는 것을 미리 알고있지만, 문제를 처음 보았을 상황을 가정해서 dp 문제풀이를 해보도록 하겠습니다. 또, 하나 dp의 사고과정을 위해 작성한 글이기 때문에 코드를 직접 작성하지 않겠습니다.  #1번째 문제: 백준10942  팰린드롬?https://www.acmic.. 2024. 7. 9.
[백준 2565] 전깃줄 / 자바 / dp + LIS 문제         레벨: G5알고리즘: dp + LIS 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/25651 번째 시도   [알고리즘 설명]이 문제는 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘을 사용하여 해결할 수 있습니다. 전깃줄이 교차하지 않으려면, B 전봇대의 연결 위치가 증가하는 순서여야 합니다. 따라서 LIS를 찾으면 교차하지 않는 최대 전깃줄의 개수를 알 수 있고, 전체 전깃줄 개수에서 이를 뺀 값이 제거해야 할 최소 전깃줄의 개수가 됩니다. 시간복잡도 O(n^2) 코드import java.util.*;import java.io.*;public class Main { public s.. 2024. 7. 8.
[백준 2096] 내려가기 / 자바 / dp + 슬라이딩 윈도우 문제         레벨: G5알고리즘: dp + 슬라이딩 윈도우 풀이시간: 1시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20961 번째 시도   [알고리즘 설명]위 방식을 어떻게 dp 로 구현하지? 아무리 생각해도 작은 문제를 해결해서 위 문제를 해결하지 못할 것 같은데 ?1줄만 있는 경우  -> 2줄만 있는 경우 - > 3줄만 있는 경우 이런 식으로 업데이트 해도 조건이 달라질 때마다 경로가 달라지는데?=> dp[]의 각 원소를 각 줄의 최적값으로 생각하지 말고, 한 줄의 세 숫자의 최적값으로 생각하자.위 고민들을 dp[] size = 3배열로 해결할 수 있다. 나는 최소, 최댓값을 구하기 위한 경로에 집착했다. 관점을 달리해 매줄 마다 세 개의 숫자에 지난 줄.. 2024. 7. 8.
[백준 14501] 퇴사 / 자바 / dp(기본) 문제         레벨:  S3알고리즘: dp(기본)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/145011 번째 시도   [알고리즘 설명]위 문제는 dp의 대표문제인 배낭문제(Knapsack Problem)와는 다르다. 배낭문제는 앞에 가방을 선택하더라도 무게 여유가 있다면 선택할 수 있지만, 위 문제는 앞에 이틀짜리 스케줄을 선택한다면 뒤에 스케줄을 선택을 못한다. 위 dp 문제는 일반적인 최소한의 일수로 최대치값을 구하는 문제와 다르다는 인지하고 들어가야 한다. 주어진 일수와 탐색 색 스케줄 두개를 기준으로 dp를 업데이트 해가는 것이 아닌 주어진 일수, 탐색 스케줄을 한 번에 묶어서 기준 한 개로 탐색해야 한다. (새로운 유형)그래서 dp의 인덱스.. 2024. 7. 6.
[백준 14500] 테트로미노 / 자바 / DFS + 구현 문제         레벨: G4알고리즘: DFS + 구현 풀이시간: 1시간 힌트 참조 유무: 유 https://www.acmicpc.net/problem/145001 번째 시도   [알고리즘 설명] 4방향 depth 4로 dfs를 해보면 'ㅜ' 모양 빼고 다 만들 수 있다.'ㅜ' 모양을 만들려면 depth가 2일 때, 즉 'ㅜ'의 중앙일 때 그 위치에서 next로 넘어가지 않고, next의 값만 +해서 파라미터에 넘겨줘 재귀를 한다. 그렇다면 dpeth는 3이 됐는데 전이랑 위치가 변함이 없고 next의 값은 반영 되어있다. 실질적으로 한 칸 갔다 온 걸로 치는 것이다. dfs 구현은 꾸준히 연습해야겠다.import java.io.BufferedReader;import java.io.IOException.. 2024. 7. 3.
[백준 13458] 시험감독 / 자바 /그리드 문제         레벨: B2알고리즘: 구현 풀이시간: 10분힌트 참조 유무: 무https://www.acmicpc.net/problem/134581 번째 시도   삼성SW역량테스트인데도 말도 안되게 쉬워 푸는 내내 경계했다. 그러나 쉬운 문제가 맞았다. 단 주의해야 하는 건 입력값이다. 입력값의 최대값을 생각해보자.B =1, C= 1, 시험장의 개수 1,000,000 x 응시자수 1,000,000  = 1,000,000,000,000 1조이기 때문에 ans를 int형으로 쓰면 틀린다.import java.io.BufferedReader;import java.io.InputStreamReader;class Main { public static void main(String[] args) throw.. 2024. 7. 3.
[백준 3190] 뱀 / 자바 / 구현 문제         레벨: G5알고리즘: 구현 + 큐 풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/31901 번째 시도: 성공   [예제 그림]초에 해당하는 뱀의 머리 위치를 그림으로 그려봤다.x는 사과의 위치다.[알고리즘 설명]이 문제는 구현 문제이다.while 문 안에 있는 조건들을 어떻게 잘 구현했는지, 자료구조를 적절히 잘 사용했는지가 관건이다. 설명은 주석을 참조바란다. 뱀의 몸통을 담기 위해 snake큐명령을 담기 위한 moves큐  문제를 다 풀고 나서 한가지 생각해본 점은 명령을 담기 위한 자료구조를 큐 말고 HashMap을 썼다면 ntdir,ntsec를 안썼어도 됐다는 거다. 변수가 줄어들수록 코드의 유지보수가 쉽다고 생각하기 때문에 다음.. 2024. 7. 3.
[백준 13460] 구슬 탈출2 / 자바 / BFS 문제         레벨: G1알고리즘: BFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/134601 번째 시도: 성공   [알고리즘 설명]처음엔 변수를 여러개 만들어 정답을 관리하려고 했다. 예를 들면, blue가 움직인 횟수, red가 움직인 횟수, blue의 움직인 경로, red의 움직인 경로 등등.  왜 이렇게 하려고 했냐면 BFS함수를 재사용하기 위해서이다. BFS(A), BFS(B) 이와 같이 말이다. 각각 함수를 돌려 리턴받은 값으로 비교하려고 했으나 복잡해져 다른 방법을 사용했다.그냥 지엽적으로 bfs 한코드에 다 넣었다. 신경써야 하는 변수들도 줄어드니 의식의 흐름대로 코드를 작성할 수 있어 수월했다. 자세한 설명은 주석으로 하겠다.imp.. 2024. 7. 3.

티스토리툴바