[알고리즘] 선분 교차 판정
선분 교차 판정은 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 *..
[백준] 9202: Boggle [Java]
알고리즘 분류: 트라이, 백트래킹문제 링크: https://www.acmicpc.net/problem/9202 【 문제 】 4*4 격자판에 알파벳들이 주어지면, 각 문자에서 8방 탐색을 해 문자열을 구성하고, 그 문자열이 찾고자 하는 문자열 리스트에 들어있는지 여부에 따라 총 점수, 가장 긴 문자열, 찾은 문자 개수를 갱신하는 문제이다.주의해야할 점은 같은 위치의 문자를 두 번 이상 사용할 수 없다(다시 방문할 수 없다)는 것, 이미 찾은 문자열에 대해서는 점수를 올리거나 문자 개수를 올리지 않는다는 점이다. 【 풀이 】찾아야 할 단어 목록을 트라이로 구성.이때 트라이 노드에 단어의 끝을 나타내는 문자인 `*` 을 넣어줬다격자판에서 인접한 문자를 고르면서 문자열을 조합해내야 하기 때문에 DFS로..
[백준] 28422: XOR 카드 게임
알고리즘: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/28422 28422번: XOR 카드 게임 XOR 카드 게임이란 $N$장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다. 한 www.acmicpc.net 【 문제 】 주어진 카드 n장 중 2장 혹은 3장을 카드가 0장이 될 때까지 뽑는다. 뽑은 카드에 적힌 숫자들을 XOR 연산한 뒤, 2진수 값으로 변환시켜 1의 개수를 구하고 점수로 더한다. 마지막에 1장의 카드가 남을 경우 최종 점수가 0점이 된다. 이때 점수의 최댓값을 구하는 문제. 【 풀이 】 1비트의 개수를 구하는 함수를 정의한다...
[프로그래머스] 연속 부분 수열 합의 개수 [Java]
알고리즘 분류: 해시맵, 누적합, 완전 탐색 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 【 문제 】 정수로 이루어진 배열이 주어졌을 때 이를 원형 리스트로 간주한다. 이때, 서로 다른 연속 부분 수열의 합의 개수를 구한다. 【 풀이】 첫 for 루프에서 연속 부분 수열의 요소 개수를 정한다. 두 번째 for 루프에서 부분 수열의 첫 요소를 제거하고, 다음 요소를 추가하면서 누적 합을 계산한다. 이때 그 누적합을 map에 저장..
