전체 글

serialVersionUID와 @SuppressWarning("serial")처리

serialVersionUID 란? 자바에서 serial version uid를 생성하는 것은 기본적으로 서로 다른 클래스들 간의 구별을 하기 위한 것이다. 동일한 이름을 가진 클래스라 하더라도 메소드나 필드가 다를 경우 서로 다른 것으로 인식하는 것이 기본이기 때문에 Object Serialization을 할 때 import/export 등에서 버전에 따라 종종 불일치 에러가 발생하는 것을 만나게 된다. @SuppressWarning("serial") Adds a default serial version ID Adds a generated serial version ID @SuppressWarnings("serial") 이 세 가지를 추천한다. 그렇다면, 이러한 warning 이 뜨는 이유는 무엇인가?..

MST

Tip 최소 스패닝 트리코드는 그냥 외우기!!!! 중요한 건 해당 문제가 MST 문제인지 알아내는 능력 모든 노드가 연결되도록한다거나 이미 연결된 노드를 최소의 비용으로 줄이기 MST Minimum Spanning Tree Spanning Tree : 모든 노드가 연결된 트리 MST : 최소의 비용으로 모든 노드가 연결된 트리 어떻게 해야 최소의 간선으로 모든 노드를 연결할 수 있는지가 관건. MST 푸는 방법 : Kruskal or Prim Kruskal : 전체 간선 중 작은 것부터 연결 (Union-Find로 구현이 가능하지만 복잡.) Prim : 현재 연결된 트리에 이어진 간선중 가장 작은 것을 추가. (상대적으로 구현 간단.) 가장 작은 것을 비교해주는 자료구조를 heap으로 사용. heap은 ..

dp

DP Dynamic Programing 이전의 값을 재활용하는 알고리즘 예시 : 1~10 숫자 중, 각각 이전 값들을 합한 값 구하기 이전의 값을 활용해서 시간복잡도 줄일 수 있음. 이전값 을 어떻게 구해야하는지에 대한 점화식이 필요. dp: 이전값 , 점화식: An = A(n-1) + A(n-2) 점화식 먼저 짜고 코드짜기, 어떻게 할지 모르겠을 땐, 하나씩 그려보면서 규칙찾기. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 출력 - 첫째 줄에 2 x n 크기의..

4. 시뮬레이션

각 조건에 맞는 상황을 구현하는 문제 지도 상에서 이동하면서 탐험하는 문제 배열 안에서 이동하면서 탐험하는 문제 별도의 알고리즘 없이 풀 수 있으나, 구현력 중요 매 시험마다 1문제 이상 무조건 출제 백준 1403 로봇청소기문제 https://www.acmicpc.net/problem/14503 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 ..