밤이 블로그

BOJ#2593 엘리베이터 * 문제https://www.acmicpc.net/problem/2593 * 풀이다익스트라를 이용해서 풀었습니다. 처음에 그래프 모델링에서 당황했는데 아래와 같이 해보았습니다.문제에 나와있는 예제에서 ArrayList elevator = new ArrayList();elevator : 각 엘리베이터에서 갈 수 있는 층 엘리베이터 1번 : [4, 7, 10]엘리베이터 2번 : [7, 12]엘리베이터 3번 : [4, 8, 12] ArrayList floor = new ArrayList();floor : 각 층에서 탈 수 있는 엘리베이터 4층 : [1, 3]7층 : [1, 2]8층 : [ 3 ]10층 : [ 1 ]12층 : [2, 3] 그리고 정점을 각 층이 아닌 엘리베이터로 정하였..

[공유] 알고리즘 공부를 입문할 때 읽으면 좋은 자료들 Algorithm Problem Solving 기초 http://slides.com/gangseoklee/aps-5#/

BOJ#1707 이분 그래프 * 문제https://www.acmicpc.net/problem/1707 * 풀이 그래프 관련 기본 문제입니다. 저는 BFS/DFS로 풀었는데, 주의할 점으로 연결 그래프와 비연결 그래프를 둘 다 고려해주어야 합니다, * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231707_BipartiteGraph/src/Main.java (BFS)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * BOJ#1707 이분 그래프 * https://www.acmicpc.net/p..

BOJ#2252 줄 세우기 * 문제https://www.acmicpc.net/problem/2252 * 풀이 어떤 일에 선/후 관계나 순서가 있으므로 위상 정렬을 이용해보았습니다. -> 위상 정렬 설명 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824 주의할 점으로는32000 * 32000 배열이 선언이 안되므로 (Heap 사이즈)ArrayList를 사용했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232252_Lineup/src import java.io.*; import java.util.*; /** * BOJ#2252 줄세우기 * https://www.acmic..

BOJ#1932 숫자삼각형 * 문제https://www.acmicpc.net/problem/1932 * 풀이 ▷ dp 정의dp[i][j] : i층에서 j 를 선택했을 때, 0~i 층의 최대값 ▷ dp 점화식dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1]) 별로 어렵지 않은 문제였지만 시간초과로 고생을 좀 했습니다. 원인으로는 dp 초기값을 0으로 설정했는데 코드 64라인에서 dp값을 재활용 할 때, 원래 삼각형 값이 0인 경우와 dp 초기값 0인 경우를 구분하지 못해서 메모이제이션을 하지 못했기 때문입니다. dp 초기값을 -1으로 고쳐서 해결하였습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/..