본문 바로가기

자바127

[백준 9466] 텀 프로젝트 / 자바 / dfs + cycle #문제         레벨: G3알고리즘: dfs + cycle풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/9466#문제 풀이        본 유형은 나에게는 신유형이다. 보통 dfs라면 cycle를 돌지 않고 한 번 간 곳은 visited[] 배열로 방문하지 않는다. 그러나 이 문제는 done[] 배열을 만들어 두 번 순회하여 dfs를 마친다. 한 번 순회로 dfs를 마칠 수 있지 않나? (그럴 수도 있을 것 같긴 하다..) 그러나. 가볍게 이해하기 위해서는 dfs를 두 번 도는 것이 좋다. 한 번 돌 때는 연결고리를 만드는 과정이고 두 번 순회할 때는 cycle인지 판별하여 팀원인지 가려내기 위함이다.  #풀이 코드      import java.io.Bu.. 2024. 7. 15.
[백준 2533] 사회망 서비스 / 자바 / dp + dfs #문제         레벨: G3알고리즘: dp + dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2533#문제 풀이        dp와 dfs를 섞은 문제이다. 이 문제에서 얻을 수 있는 점은 두가지이다.첫 째, 그래프를 배열로 표현하는 것. 둘 째, 큰 문제를 작은 문제로 쪼개는 방법.셋 째, vistied배열 대신 parentNode로 판별하는 방법(중복 탐색 예방)넷 째, dp 구현방식위 문제는 dp[node][0], dp[node][1]를 가지는 이차원 배열로 풀어내야 한다. 가장 아래에 있는 리프 노트부터 시작하여 루트 노드의 dp 값을 채우는 방식이다.  예를 들면 dp[5][0] 은 노드 5가 얼리어답터가 아닐 때이다. 그러니 반드시 부모(.. 2024. 7. 11.
[백준 11066] 파일 합치기 / 자바 /dp #문제         레벨: G5알고리즘: dp 풀이시간: 1힌트 참조 유무:https://www.acmicpc.net/problem/11066#문제 풀이        그리드 문제로도  착각할 수 있지만 연속된  파일들만 합칠 수 있기 때문에 그리드 문제는 아니다. (그리드 문제라면 파일을 합치고 정렬하고 합치고를 반복하기 때문에 연속된 파일임을 보장하지 않음) dp[i][j] =  i ~ j까지 파일 합쳤을 때 최솟값+행은 시작인덱스를 나타내고 열은 끝인덱스를 나타낸다.{2,3}이면 2에서부터 3까지 더했을 때 최솟값이다. dp 배열을 이 방향으로 채워진다. 빨간색 숫자는 채워지는 순서를 뜻한다. 아래 코드르 보면 알겠지만 이중 for문이 뜻하는 것은 파란색 방향을 말하는 것이다.가장 깊숙히 있는 fo.. 2024. 7. 10.
[백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp #문제         레벨: G4알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14002#문제 풀이         [1번째 시도: 실패]멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.package project;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2024. 7. 10.
[백준 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.

티스토리툴바