전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW를 이용한 선분 교차 판정 문제입니다. 선분이 나타날 수 있는 2경우입니다.(두 선분이 겹치는 경우는 제외했습니다,) 선분이 교차되는 경우와 아닌 경우가 있습니다. 여기서 확인할 수 있는 것은 한 점에서 다른 선분을 향할 때의 방향이 다르면 선분이 교차하지 않는다는 것입니다. 어느 점에서의 방향을 구하는 방법은 CCW입니다. 따라서 A,B,C / A,B,D의 CCW를 구한 뒤, 곱한 것과 C,D,A / C,D,B를 구한뒤 곱한 것이 ..

문제 링크입니다. https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 선분 교차를 판정하는 문제입니다. CCW를 이용하는 문제입니다. 선분이 교차되는 경우와 아닌 경우가 있습니다. 여기서 확인할 수 있는 것은 한 점에서 다른 선분을 향할 때의 방향이 다르면 선분이 교차하지 않는다는 것입니다. 어느 점에서의 방향을 구하는 방법은 CCW입니다. 따라서 A,B,C / A,B,D의 CCW를 구한 뒤, 곱한 것과 C,D,A / C,D,B를 구한뒤 곱한 것이 0또는 음수가 나온..

문제 링크입니다. https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net CCW를 이용하는 문제입니다. CCW라는 기하 알고리즘을 사용하는 문제입니다. https://degurii.tistory.com/47 에 잘 나와있으니 참고해주시면 감사하겠습니다. [알고리즘] CCW로 세 점의 방향성 판별하기 0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/5597 5597번: 과제 안 내신 분..? X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, www.acmicpc.net 배열을 이용해 푸는 문제입니다. 28명의 학생 출석번호를 입력받고, 빠진 2명이 누구인지 구하는 문제입니다. 배열을 이용하여, 배열에 값을 저장하는 방식으로 풀면 됩니다. 입력받은 학생은 존재한다는 의미이니, 해당 칸에 1의 값을 넣어줍니다. 마지막에 1~30까지 칸을 확인할 때, 0인 칸이 있다면 빠진 학생이라는 것이 됩니다. 자세한 것은 코드를 참고해주세요 #de..

문제 링크입니다. https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net 배열 혹은 Map을 이용하면 쉽게 풀 수 있는 문제입니다. 기본 문제라고 할 수 있는 쉬운 문제입니다. 수가 주어졌을 때, 찾는 수가 얼마나 있는지를 구하는 문제입니다. 푸는 방법은 배열을 이용해 모든 수를 저장한 뒤, 배열 속에서 일치한 수를 찾는 방법이 있습니다. 다른 방법은 Map을 사용하면 더 쉽게 풀 수 있었습니다. 자세한 것은 코드를 참고해주세요 #defi..

문제 링크입니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 중간에서 만나기 방법을 사용하는 문제입니다. 배열 A, B, C, D에서 수를 한 개씩 뽑아 합이 0이 되게 만드는 문제입니다. 배열의 크기가 크기 때문에 모든 경우를 탐색하기에는 무리가 있습니다. 따라서, (A+B) / (C+D)로 나눠서 합을 구한 뒤, 둘을 합치는 방법을 사용합니다. 두 배열에 있는 수를 더하는 것이기에 합이 같은 경우가 있을 수 있습니다...

문제 링크입니다. https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net MAP을 사용하면 쉽게 풀 수 있는 문제였습니다. 숫자 카드 중, 가장 많은 카드를 구하는 문제입니다. 카드를 입력 받으면서 map을 통해 해당 카드의 갯수를 증가합니다. 마지막에 map을 통해 for문을 이용하면서 가장 많으면서 작은 수를 구해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제 링크입니다. https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net python을 이용하면 굉장히 쉽게 풀 수 있겠지만, C or C++은 자료형에 수의 한계가 정해져 있습니다. 따라서 큰 수 계산을 위한 코드를 짜야했던 문제입니다. 접근 방법은 먼저, 두 수를 뒤집습니다. 1의 자리부터 계산하기 위함입니다. for문을 통해 1자리씩 넘어가면서 계산을 합니다. 한자리수의 합을 계산한 뒤, 이를 string을 사용한 정답에 계속 이어 붙여주는 방법입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #includ..

문제 링크입니다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹을 이용한 문제였습니다. 주어진 알파벳을 통해 암호를 만드는 문제입니다. 암호가 되는 조건은 모음이 1개 이상, 자음이 2개 이상입니다. 나올 수 있는 모든 경우를 출력하는 것이기에 백트래킹을 사용하면 됩니다. 또한, 출력은 사전 순이기에 백트래킹을 시작하기 전에, 오름차순 정렬을 해주고 시작하면 편하게 코드를 짤 수 있습니다. 자세한 것은 코드를 참고해주세요 #define _..

문제 링크입니다. https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net '중간에서 만나기' 를 사용하는 문제입니다. 가방에 물건을 C이하만큼 넣을 수 있습니다. 하나의 물건에서 할 수 있는 경우는 선택O / 선택X인 2가지입니다. 물건이 총 30개까지 주어지니, 전체의 경우는 2^30입니다. -> 시간초과가 생깁니다. 따라서, 문제를 풀기 위해선 '중간에서 만나기'를 사용해야합니다. 중간에서 만나기란, 전체 경우를 2가지로 나눠서 생각하는 것입니다...

문제 링크입니다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net '중간에서 만나기' 방법을 사용하는 문제입니다. 중간에서 만나기에 대해 잘나와있는 설명입니다. 해당 블로그를 참고해주세요 -> https://restudycafe.tistory.com/523 문제에서 N의 값은 최대 40입니다. 수는 선택하거나 선택하지 않는 2가지 방법이 있습니다. 그렇다면 모든 경우의 수를 확인해보려면 2^40이 나오게 ..

문제 링크입니다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS를 사용한 문제입니다. 해당 문제에서 변형된 문제이니, 문제를 풀고 와주시면 좋을거 같습니다. -> https://junseok.tistory.com/170 LCS 문제에서 추가된 것은 수열까지 출력하는 것입니다. 쉽게 생각할 수 있는 방법은 수열을 저장하면서 푸는 방법인데 이는 시간초과로 실패했습니다. 따라서 역추적을 하는 ..