Better

https://www.acmicpc.net/problem/2352

LIS, 동적계획법, 그리디 알고리즘 등으로 풀수 있는 문제입니다.

저는 LIS로 접근해봤습니다.

첫번째 원소를 결과배열에 넣고 시작합니다.

두번째 원소부터 배열의 마지막 값과 비교해서 해당원소가 더 크면 뒤에 추가,

작으면 앞에서부터 해당 원소보다 처음으로 같거나 큰 배열값을 만났을때 교체 하는 식으로 접근했습니다.

포트번호가 4 2 6 3 1 5

에서 가장긴 증가하는 부분수열을 구하면

2 3 5가 되는데 이번 문제를 푸는 방식으로 구해보면 1 3 5 가 나옵니다.

선이 겹치지 않아야 하는데 이 부분에서 고민이 많이 됐습니다.

답은 최대 길이만 구하면 되므로 통과되는데 선의 겹침을 해결하지는 못했습니다.

이 부분을 고민중입니다..

https://www.acmicpc.net/problem/2644

BFS를 사용해 촌수를 계산하는 문제입니다.

각 사람의 정보와 촌수를 저장하는 클래스를 만들어 사용했습니다.

시작을 x, 촌수 0으로 시작해서 연결된 사람이 있으면 현재촌수 + 1 해주며 큐에 담습니다.

BFS진행 중 y차례가 되면 촌수를 저장하고 BFS를 종료합니다.

https://www.acmicpc.net/problem/14888

재귀호출을 사용하는 브루트포스 문제였습니다.

매번 각 연산자의 숫자를 solve함수에 넣어주면서 재귀호출을 해줍니다.

재귀호출로 만들어지는 경우의 수를 보면

연산자의 수가 (+ - * /) 각각 2 1 1 1 일때

1. + + - * /
2. + + - / *
3. + + * - /
4. + + * / -
5. + + / - *
6. + + / * -
7. + - * / +

이런 순서로 진행 됩니다.

재귀호출을 이해하는것이 포인트인 문제 같습니다.

https://www.acmicpc.net/problem/3053

택시 기하학 에 대해 알아가는 문제였습니다.

그림 출처 : 위키백과

T1(x1,y1),  T2(x2,y2)

기존 유클리드 기하학에서 두점의 거리는 길을 가로지르는 초록색 선이고 최단거리입니다.

하지만 모눈종이의 길을 따라 가는 빨강,초록,노랑의 길이는 모두 같습니다.

이것이 택시 기하학(맨해튼거리)입니다.

문제에 택시 기하학 공식으로 나온 D(T1,T2) = |x1-x2| + |y1-y2| 으로 빨간길의 길이를 재보면

이해가 쉽습니다.

원

원이란 한지점에서 거리가 일정한 점들의 집합입니다.

유클리드 기하학에서 원은 일반적으로 알고 있는 둥그란 원입니다. (원의 넓이 : pi*R^2)

택시 기하학에서 원은 택시 기하학적으로 거리가 같은 점들의 집합이로 마름모 꼴이 나옵니다.

그림 출처 : 조선뉴스프레스 - 월간조선

그림을 보면 원점에서 선을 따라 각 면에 다다르는 길이는 모두 같습니다.

이처럼 택시 기하학에서 원이란 마름모 꼴입니다.

즉, 택시 기하학에서 원의 넓이는 마름모의 넓이를 구하면 됩니다. (마름모 넓이 : 2R^2)

https://www.acmicpc.net/problem/1057

수학 문제였습니다.

a와 b가 같아질때까지 카운트해주면 됩니다.

1번 vs 2번 승자 => 다음라운드 1번 부여 : (1+1)/2, (1+2)/2

3번 vs 4번 승자 => 다음라운드 2번 부여 : (3+1)/2, (3+2)/2

x번 vs x+1번 승자 => x승리시 : (x+1)/2번, x+1승리시 : (x+2)/2번 부여

(x는 홀수)

https://www.acmicpc.net/problem/10825

간단한 정렬 문제였습니다.

학생정보를 담는 클래스를 만들어 저장했습니다.

그 후, Arrays.sort()로 오름,내림 차순 정렬해주었습니다.

국어 : 내림차순

영어 : 오름차순

수학 : 내림차순

이름 : 사전순 오름차순

으로 정렬합니다.

(* 오름차순 1,2,3,4..... 갈수록 증가)

(*내림차순 4,3,2,1.... 갈수록 감소)

*Comparator 인터페이스의 compare메소드를 오버라이드하여 사용합니다.

오름차순 정렬은

o1>o2 면 1 (양수)

아니면 -1 (음수)를 리턴합니다. 

1 이면 자리바꿈, -1이면 자리유지 입니다.

내림차순을 하고싶으면 o2 와  o1의 자리를 바꿔줍니다.

(* 문제에서 o1==o2일 경우의 조건을 달아주어서 같을때 0을 리턴하는게 아니라 조건문을 달아 주었습니다. 일반적으로 같을경우 0을리턴해 자리를 유지합니다.)

https://www.acmicpc.net/problem/1937

DFS + DP 문제였습니다.

dp[y][x] 에 (y,x)지점에서 살수있는 최대 일 수 를 저장합니다.

dfs로 재귀호출 을 하면서 dp[y][x]값을 지정해줍니다.

시간을 고려하기 위해 DFS에 DP를 적용시켜 문제를 풀어야 합니다.

즉, 방문했던곳이면 바로 dp[y][x]에 저장된 최대일수를 리턴합니다.

ex)

[map]

시작지점을 (0,0)으로 해보면

dp[0][0] = max(dp[0][0], dfs(0,1) + 1) = 5

dp[0][1] = max(dp[0][1], dfs(0,2) + 1) =4

dp[0][2] = max(dp[0][2], dfs(1,2) + 1) =3

dp[1][2] = max(dp[1][2], dfs(1,1) + 1) =2

dfs(1,1) -> 갈 곳이 없음 -> return dp[1][1] (= 1)

dfs(1,1) 이 1로 리턴되므로 역으로 올라가면 2, 3, 4, 5 가 되어 dp[0][0]은 5가 됩니다.

만약 시작지점을 (1,0)으로 한다면 dp[1][0] = max(dp[1][0], dfs(0,0)+1) 인데

dp[0][0] 의 값이 5로 저장되어 있으므로, return dp[0][0] 로 재귀호출을 바로 끝냅니다

따라서 do[1][0] 은 5 + 1 = 6 이 됩니다.

[dp]

https://www.acmicpc.net/problem/12100

브루트포스와 DFS를 같이 사용하여 해결한 문제입니다.

dfs를 호출할때마다 현재 map의 상태를 기억해주어야 모든 경우의 수를 따져볼 수 있습니다.

map 의 상 하 좌 우 이동은 move()함수를 통해 이동시켜줍니다.

* 맵을 이동시킬때 Queue를 사용하는데,

상,하 방향일땐 각 열의 모든원소를 큐에 담고,

좌,우 방향일땐 각 행의 모든원소를 큐에 담습니다.

idx변수를 사용해 상,하 일때 행, 좌,우 일때 열 을 지정해주면 해당 블록의 위치가 지정됩니다.

(이때 이동방향에 있는 블록이 우선순위인걸 생각해줍니다 idx -> 상: 0, 하: n-1, 좌: 0, 우: n-1)