백준 문제풀이 (7) 썸네일형 리스트형 BOJ 5615 아파트 임대[C++] 먼저 문제에서 주어진 식을 변형해야 한다. 아파트의 면적을 n이라 놓으면 2xy + x + y = n. 양변에 2를 곱하고 1을 더하면 4xy + 2x + 2y + 1 = 2n + 1. 좌변을 인수분해하면 (2x + 1)(2y + 1) = 2n + 1. 문제에서는 불가능한 아파트 면적을 찾는 것이다. x,y의 조건에서 2x+1, 2y+1모두 3이상의 홀수이고 이때 가능한 2n + 1 값은 3이상의 홀수 두개로 소인수분해된다. 즉 불가능한 2n + 1값은 3이상의 홀수 두개로 소인수분해 되지 않는 수인데, 2x + 1 과 2y + 1은 짝수가 나올 수 없으므로 둘 중 하나가 3보다 작은 홀수, 즉 1이다. 따라서 2n +1 의 값이 1 x (1이 아닌 홀수) 로만 인수분해 할 수 있는 수 즉 소수가 될때,.. BOJ 3665 최종 순위 [C++] 위상정렬 문제이다. 하지만 문제에서 주어진 입력에서 각 팀 사이의 관계를 추출하는 것이 어려웠다. #include using namespace std; int main() { int tt; cin >> tt; for (int ttt = 0; ttt > n; vector same(n + 1,true); vector next[501], pre(n + 1), temp; map rank,high,low; for (int i = 0; i > buf1; temp.push_back(buf1); rank[buf1] = i + 1; low[buf1] = i + 1; high[buf1] = i + 1; } cin >> .. BOJ 16566 카드 게임 [C++] 규칙이 길고 복잡해 보이지만, 사실 별거 없는 문제다. 규칙에서 문제 풀이에 필요한 정보만 추출해내면, 철수는 1~N까지 숫자가 적힌 카드중 아무거나 낼 수 있다. 민수는 철수의 카드보다 큰 숫자가 적힌 카드를 내야한다. 문제 입력은 첫째줄에 n, m(민수 카드 개수), k(철수가 내는 카드 개수)가 주어지고 둘째줄에 민수의 카드, 셋째줄에 철수의 카드가 주어진다. 출력은 철수의 각각 카드에 대한 것이므로 k개 줄에 걸친다. 민수의 카드중 철수의 특정 카드보다 큰 카드를 파악하기 위해서는 먼저 민수 카드의 배열을 정렬해야한다. 그리고 철수 카드보다 큰 카드의 위치를 알려줄 것인데, 이때는 앞에서부터 차례대로 탐색하는 방법이 있지만 이는 시간복잡도가 최대 O(M)에 달할 수 있어 비효율적이다. 따라서 이분.. BOJ 9328 열쇠 [C++] 또한 빡센 구현, 시뮬레이션 문제이다. 요즘 문제가 어려워질수록 구현 자체의 난이도도 높아지는 듯 하다. 이 문제는 특히 문자를 사용해서 손도 대기 꺼리게 만드는 것 같다. 먼저 시간복잡도는 고려하지 않아도 된다. 완전탐색도 아니고 문제 사이즈도 작은데다, bfs자체가 그리 오래걸리지 않는다. 아래 코드로 8ms 소비하여 AC를 받았다. 문제는 먼저 건물 지도를 입력받는다. 입력받을 때 문이 있다면, 그 문의 좌표를 문의 종류에 맞는 doors라는 벡터에 삽입해준다. 상근이에게 처음 주어진 열쇠는 종류에 맞는 문이 존재한다면 그 문을 모두 연다. 당장 문에 도달하지 못한다고 해도 추후에 그 문에 도달하면 문을 열 것이므로 그냥 다 연다. 여기서 효율성을 좀더 높이려면 열린 문은 벡터에서 빼버려도 된다. .. BOJ 17387 선분 교차 2 [C++] 까다롭고 복잡한 문제다. 그리고 문제를 푸는 핵심 개념이 ccw라는 것인데 함수에 이런 값을 넣으면 이렇게 튀어나오는구나 정도만 이해했지 공식 내용은 이해하지 못했다. 그래서 선형대수학 공부를 좀 하려한다. 아무튼 ccw함수는 (2차원이라 가정) 세점 p1, p2, p3를 입력받으면 p1, p2, p3로 가는 경로가 시계방향이면 -1, 반시계는 1, 직선이면 0 을 반환하는 함수다. 이것을 4번하고 곱하고 비교해서 두 직선이 평행하지 않을때 교차 여부는 입력된 4개의 좌표의 값들을 ccw만 돌리고 직접 대소비교하지 않고도 쉽게 판단할 수 있다. 하지만 평행할때는 좀 까다롭다. 내가 놓쳐서 헤맸던 가장 큰 것이 입력시 x1 < x2, x3 < x4, y1 < y2, y3 < y4가 보장되지 않는다는 것이다.. BOJ 1918 후위 표기식 [C++] 고생 많이 한 문제였다. 먼저 처음 접하는 내용이라 문제 자체가 직관적으로 와닿지가 않았다. 그래서 작게 분해해서 풀기로 했다. 알고리즘 분류는 스택이라 되어있는데 재귀함수를 사용했다. 뭐 재귀함수도 결국 스택이니까. 수학에서 연산자 우선순위는 () > */ > +-순서이다. proc 함수 내부에서 이 세 연산자를 순서대로 처리하도록 하고 괄호의 경우 괄호 내부의 식을 다시 proc 함수의 파라미터로 전달해 재귀호출하였다. 괄호 안에 괄호가 또 있고 짝이 맞지 않는 닫힘괄호에 의해 잘못된 ss값을 구하는 것을 방지하기 위해 스택과 비슷한 원리로 열림 괄호는 n++, 닫힘괄호는 n--를 해주었다. 그리고 괄호를 처리하여 각각의 문자열을 문자열 벡터 vec에 넣어주었다. vec의 각 값은 문자 하나가 될 수.. BOJ 9663 N-queen [C++] 처음 글을 써본다. 브루트포스 알고리즘. 무식하게 푼다는 뜻이다. 근데 정말 무식하게 풀어서 이문제를 3시간 걸렸다. 먼저 체스를 해본적이 없어서 퀸이 어떻게 움직이는지 알아봤다. 무식하게 순서만 다른 같은 경우의 수를 확인을 못했다. 그리고 또 무식하게 O(n^2)짜리를 재귀함수 안에 넣었다. 이 문제는 위에서 한 행씩 내려가면서 퀸을 놓을 위치 한개씩을 선택하면 된다. 그 과정에서 두 대각선 방향과 이미 방문된 열인지 체크해주면 된다. 이 과정을 좀 쉽게 하기 위해 수학을 곁들이면 좌표평면에서 x,y절편이 같도록 기울기가 -1인 직선을 그으면 그 직선 위 모든 좌표의 x,y좌표의 합은 일정하다. 이 원리를 적용해 대각선 방문 여부를 쉽게 저장할 수 있다. 아래는 시행착오가 담긴 무식한 코드 + 디버깅.. 이전 1 다음