[백준] 7578: 공장[Java]
알고리즘 분류: 세그먼트 트리, 자료구조문제 링크: https://www.acmicpc.net/problem/7578 어떻게 풀어야 할까.. 막막하지만역전(inversion) 이라는 개념을 알고 있으면 정말 쉬워진다.역전(inversion)은 배열에서 앞에 있는 값이 뒤에 있는 값보다 큰 경우를 말하기도 하고,원본 배열과 비교 배열에서 원본 배열의 요소가 비교 배열의 요소에서 얼마나 뒤로 떨어져 있는지를 의미하기도 한다. 풀이는 굉장히 간단한데, 그냥 inversion된 애들이 얼마나 inversion 되었는지 세어주면 된다. 어차피 모든 요소들이 매칭이 되어야하므로어떤 요소가 inversion 되지 않았다면(뒤에 위치하고 있다면)?어떤 요소는 반드시 inversion 되어 있는 상태가 된다. 위..
알고리즘 분류: 구현, 시뮬레이션문제 링크: https://www.acmicpc.net/problem/21609 구현이 은근히 쉽지 않았던 문제. 일단 문제는 그냥 주어진 로직을 순서대로 구현하면 된다.필요 로직은 다음과 같다. 1. 그룹핑2. 그룹 중 가장 블록 개수가 많은 그룹 없애기(-2 로 설정했음) 3. 이때 그룹들의 블록 개수가 모두 2 미만이라면 종료4. 블록 개수의 제곱만큼 점수를 더한다.5. 블록 내리기6. 왼쪽으로 90도 회전7. 블록 내리기8. 1번으로 다시 돌아간다. 이때 주의할 점은그룹핑 할 때는 무지개 블록을 기준으로는 하면 안된다는 점,기준 블록은 무조건 그룹핑을 시작한 블록 기준이라는 점(그래서 그냥 배열을 순서대로 순회하면 된다)그룹핑 하고 나서는 무지개 블록은 방문 처리..
[백준] 15989: 1, 2, 3 더하기 4 [Java]
알고리즘 분류 : DPhttps://www.acmicpc.net/problem/15989 정수 n을 1, 2, 3의 합으로 표현하는 방법의 수를 구하는 문제이다.각각의 경우에서 숫자는 1, 2, 3을 한 번에 하나씩만 더해 나가며 만들 수 있다.여기서 주의할 점은 순서만 다르고 합을 이루고 있는 요소가 같은 경우는 카운트에서 제외해야한다. 일단 n=1, 2, 3일 때를 살펴보자. n=1 일 때,1=1경우의 수는 1가지이다. n=2일 때2=1+12=2경우의 수는 2가지이다. n=3일 때,3=1+1+13=1+23=3경우의 수는 3가지이다. 얼핏 보면, n=3일 때를 보면 n=2일 때에서 +1을 붙인 경우, n=1일 때에서 +2을 붙인 경우, n=0일 때에서 +3을 붙인 경우가 보이는 것을 알 수 있다...
[알고리즘] 선분 교차 판정
선분 교차 판정은 CCW를 활용하여 두 선분이 교차하는지를 판단하는 테크닉이다. https://baehoon.tistory.com/96 CCW를 간단히 설명하면, 세 점 A, B, C가 주어지면 벡터와 외적을 이용해 A -> B -> C로 가는 방향이 일직선인지 반시계 방향인지 시계 방향인지 세 가지 경우의 수로 나누는 알고리즘이다. CCW의 반환값은 다음과 같이 도출될 수 있었다. $$ CCW=(x2-x1)(y3-y1)-(y2-y1)(x3-x1) $$\( CCW 세 점의 진행 방향이 시계 방향이다. \( CCW>0 \) => 세 점의 진행 방향이 시계 방향이다. \( CCW=0 \) => 세 점의 진행 방향이 시계 방향이다. 코드는 다음과 같다. int ccw..
[알고리즘] CCW(Counter-Clock-Wise)
CCW(Counter Clock Wise) 알고리즘은 세 개의 점을 이은 직선의 방향을 알고자 할 때 유용한 알고리즘이다.기하 알고리즘의 기초라고 볼 수 있는데, 2차원 평면 위에 놓인 3개의 점이 어떤 방향성이 있는지 알려주고 이를 통해 이후 선분 교차 판정이나 볼록 껍질 등에 활용할 수 있다. 이 알고리즘은 3가지 경우의 수를 나타낸다.반시계 -> 왼쪽으로 도는지시계 -> 오른쪽으로 도는지일직선 CCW를 이해하기 위한 사전 지식에는 벡터와 외적이 있다. 벡터는 두 점을 잇는 화살표이다.어디에서 시작해 어디로 가는지, "방향"과 "크기"를 가지고 있다.A라는 점에서 B라는 점으로 가는 화살표가 있다면 이는 \(\overrightarrow{AB}\) 로 표현될 수 있다. 외적은 두 점 A,B가 있을 때..
[백준] 19585: 전설 [Java]
알고리즘 분류: 트라이, 해싱문제 링크: https://www.acmicpc.net/problem/19585 【 문제 】 색깔을 의미하는 문자열 c개와 유저의 닉네임 n개가 주어진다.이후 팀원들의 닉네임이 n개가 주어질 때, 색상 이름과 닉네임이 순서대로 주어진 목록에 있는지 확인하는 문제이다. 【 풀이 】 정말 쉽지 않은 문제였다.정답을 맞히는데 까지 총 3번의 리팩토링을 거쳤다. 1. 색깔은 정방향으로 트라이 탐색, 닉네임은 역방향으로 트라이 탐색 이 풀이가 거의 10분 만에 생각나서 날먹하려 했지만.. 당연히 시간초과가 났다쿼리 20000개, 색깔과 닉네임 개수 4000개, 그리고 문자열 길이 각각 1000글자 싹이니, 색깔의 길이를 L, 닉네임 길이를 K라고 한다면이 풀이는 시간 복잡도 O(q *..
