본문 바로가기

Algorithm44

[백준] 11758. CCW / Java https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 풀이 이 문제는 두 벡터의 외적을 구하는 공식으로 풀 수 있는 문제이다. 일명 '신발끈 공식'으로 (빨간색 빗금으로 이어진 것들의 곱의 합) - (파란색 빗금으로 이어진 것들의 곱의 합) 이다. 즉, 아래와 같은 식이다. (x1*y2 + x2*y3 + x3*y1) - (y1*x2 + y2*x3 + y3*x1) 계산 결과가 양.. 2023. 6. 20.
[백준] 9663. N-Queen / Java https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 이 문제는 크기가 N * N인 체스판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제이다. 기본적으로 BruteForce 유형이나 isPromising()과 같은 메서드를 활용하여 가망이 없는 경로를 가지치기 하며 진행하는 BackTracking 기법이 가미되어 있다. 우선 눈여겨 볼 점은 이 차원으로 이루어진 체스판을 일 차원 배열(board[])로 바꾸어 생각한다는 것이다. 배.. 2023. 6. 14.
[백준] 14503. 로봇 청소기 / Java https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 풀이 구현 카테고리에 있던 문제라 그저 구현으로 풀수도 있었지만 DFS를 활용해서도 풀 수 있었다. 문제에 주어진 조건을 찬찬히 읽고 이해하는 것이 중요했다. 풀이 흐름에 대한 상세 설명은 소스 코드에 주석으로 대체한다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; imp.. 2023. 6. 8.
[백준] 1339. 단어수학 / Java https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 알파벳에 0~9 사이의 수를 대입하여 가장 큰 수를 만드는 문제이다. 핵심은 높은 자릿수에 위치한 알파벳에 큰 수를 맵핑하는 것이다. 예를 들어 아래 두 단어가 주어졌을 때, GCF ACDEB 알파벳별로 따로따로 생각해보면 다음과 같다. GCF = 100*G + 10*C + 1*F ACDEB = 10000*A + 1000*C + 100*D + 10*E + 1*B 그 다음으로는 알파.. 2023. 6. 1.

티스토리툴바