본문 바로가기

전체 글

백준 - 1932 정수 삼각형(Java) https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net DP 문제입니다. 문제에 의하면 위에서 부터 좌측 하단 또는 우측 하단 둘 중 하나를 선택하여 최하단으로 내려왔을 때, 합이 최대가 되게 만들어야 합니다. 이를 반대로 생각하면 현재 위치에서의 최대는 좌측 상단 또는 우측 상단의 최대를 선택해 현재를 더하면 됩니다. 현재를 (i, j)라고 했을 때, 좌측 상단 및 우측 상단의 좌표 값은 다음과 같습니다. 좌측 상단 : (i-1, j-1) 우측 상단 : (i-1, j) 즉, 점화식은 dp[i][j] = max(dp[i-1.. 더보기
백준 - 15661 링크와 스타트(Java) https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 백트랙킹(Backtracking) 문제 입니다. 백트랙킹이란, 탐색을 하면서 조건에 맞지 않는 부분을 가지치기하여 탐색의 범위를 줄이는 방법입니다. 그렇기 때문에 완전 탐색에 비해 메모리 및 시간에 이점이 있습니다. 이 문제에 두 가지 팀이 있으며, 2차원 배열이 주어졌을 때 두 팀간의 격차를 구하는 문제입니다. 2차원 배열 안에 적혀져 있는 값들은 행.. 더보기
백준 - 11779 최소비용 구하기 2(Java) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라(Dijkstra) 문제입니다. 시점과 종점이 주어지고 최소 비용 및 해당 경로의 크기, 경로를 출력을 요구하고 있습니다 기본적인 다익스트라의 기본 개념은 "돌아갈 경우가 더 비용이 적게 들 경우 돌아간다" 입니다. 비용을 1차원 int 배열에 저장시켜 계속 최소 비용을 계산해 갱신시키는 방법을 사용합니다. 최소 비용을 저장하는 1차원 int 배열은 비용에.. 더보기
백준 - 11909 배열 탈출(Java) https://www.acmicpc.net/problem/11909 11909번: 배열 탈출 상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다. 배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1] www.acmicpc.net DP 문제입니다. N이 주어졌을 때, 2차원 배열 (1, 1)에서 특정 조건을 따르면서 (N, N)까지 가는 최소 경로를 구하는 문제입니다. 문제 조건은 백준 문제에 잘 적혀있으니 추가적인 설명은 하지 않겠습니다. (문제 아래에 힌트가 있으니 문제가 이해가지 않으면 참고하시기 바랍니다.) 단, 주의해야 할 점은 현재 숫자가 이동 하려는 위치의 숫자보다 커야합니다.. 더보기
백준 - 17070 파이프 옮기기1(Java) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net DFS 문제입니다. 기본 DFS 문제들은 한 칸씩만 고려해 문제를 풀 수 있었지만, 이 문제는 파이프가 두 칸을 차지하길래 어떻게 풀어야할지 고민을 많이 했습니다. 하지만, 여기에 함정이 있습니다. 파이프는 처음에 두 칸을 먹지만, 파이프 끝을 기준으로 한 칸씩만 움직이고 있습니다. 또한, 처음 시작 위치는 (1,1)로 고정입니다. 문제에 "가장 처음에 파이프는 (1, 1.. 더보기
자바의 정석 - 12.3 애너테이션(annotation) 12.3.1 애너테이션이란? 프로그램의 소스코드 안에서 다른 프로그램을 위한 정보를 미리 약속된 형식으로 포함시킨 것 프로그램 자체에는 아무런 영향일 끼치지 않음 @Test // 이 메서드가 테스트 대상임을 테스트 프로그램에게 알림 public void method(){...} 해당 프로그램에 미리 정의된 종류와 형식으로 작성해야 의미가 있음 JDK에서 제공하는 표준 애너테이션은 주로 컴파일러를 위한 것임 12.3.2 표준 애너테이션 종류 @Override 메서드 앞에만 붙일 수 있음 조상의 메서드를 오버라이딩하는 것이라는걸 컴파일러에게 알리는 역할을 함 @Override void parentmethod() @Deprecated 더 이상 사용하지 않는 것을 권장한다는 의미임 @Deprecated int .. 더보기
자바의 정석 - 12.2 열거형(Enums) 12.2.1 열거형이란? 서로 관련된 상수를 편리하기 선언하기 위해 것임 class Card{ enum Kind {CLOVA, HEART, DIAMOND, SPADE}; enum Value {TWO, THREE, FOUR}; final Kind kind; final Value value } 여러 상수를 정의할 때 사용하면 유용함 열거형은 값과 타입을 관리하기 때문에 논리적인 오류를 줄일 수 있음 상수의 값이 바뀌더라도 기존의 소스를 다시 컴파일하지 않아도 됨 12.2.2 열거형의 정의와 사용 정의 enum 열거형이름 {상수명1, 상수명2,...}; // 예시 enum Direction {EAST, SOUTH, WEST, NORTH}; // 사용 class Unit{ Direction dir = Direc.. 더보기
자바의 정석 - 12.1 지네릭스(Generics) 12.1.1 지네릭스란? 다양한 타입의 객체를 다루는 메서드나 컬렉션 클래스에 컴파일 시의 타입 체크를 해주는 기능임 장점 타입 안정성을 제공함 타입체크와 형변환을 생략할 수 있으므로 코드가 간결해짐 12.1.2 지네릭 클래스의 선언 class Box{ T item; void setItem(T item){this.item = item;} T getItem() {return item;} } Box에서 T를 타입 변수(Type Variable)라 함 💡 T가 아닌 다른 것을 사용할 수 있으나, 상황에 맞게 의미있는 문자를 선택해야 함 타입 변수는 임의의 참조형 타입을 의미함 지네릭이 도입되기 이전의 코드와 호환을 위해 지내릭 클래스인데도 예전 방식으로 객체를 생성하는 것이 허용됨 Box b = new Box.. 더보기

티스토리툴바