Go Lang/Algorithm

개요 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제는 다음과 같습니다. 평면에 점들의 집합인 P가 있고 여기에는 N개의 좌표가 있다, N은 짝수이다. 집합 P에서 N개의 벡터를 만들 수 있다, 즉 벡터는 N/2개이다. P에서 나오는 벡터들의 합 중 최솟값을 출력해라. 이 문제를 풀려면 우선 🔍벡터의 합은 어떻게 구하는가? 벡터의 값은 끝점 - 시작점으로 구할 수 있습니다. 벡터 v1는 x1, y2에서 x2, y2로 향한다 v1 ..

개요 문제 https://www.acmicpc.net/problem/1005 📃 해당 문제는 이전에 풀었던 위상 정렬 문제인 2252번을 이용하시면 쉽게 이해할 수 있습니다. https://seung.tistory.com/entry/GoLang-%EB%B0%B1%EC%A4%80-2252%EB%B2%88-%EC%A4%84-%EC%84%B8%EC%9A%B0%EA%B8%B0%EC%9C%84%EC%83%81%EC%A0%80%EB%A0%AC [GoLang] 백준 2252번, 줄 세우기(위상 정렬) 개요 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음..

개요 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 처음 이 문제를 보고 골치가 아플 것 같았는데 유심히 보니 정답률이 높아서 계속 문제를 읽었더니 이 문제는 낚시가 있어서 이 부분만 안 속으면 매우 쉽습니다. 문제가 아래처럼 주어진다면 뭔가 아래처럼원 사이를 구불구불 지나가야 제대로 푼 거 같은 기분이 들지만 사실 아래처럼 간단하게 뒤로 돌아간다는 경우의 수가 항상 존재합니다! 즉 문제에서 말한 행성의 경계에 진입/이탈하는 경..

개요 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 📃 해당 문제는 위상 정렬로 해결할 수 있습니다. 이를 알 수 있는 이유는 키를 비교하는 것이기에 만약 1번이 2번보다 작다, 2번은 3번보다 작다 근데 3번이 1번 보다 작다와 같이 순환되지 않는다는 걸 의미합니다 거기에 문제에서 답이 여러 가지인 경우 아무거나 출력한다고 말했으니 그 말은 비교했을 때 순서가 동일한 게 생긴다는 의미입니다. 이걸로..

개요 https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 이 문제는 제곱수는 구하는 문제라 쉽게 자료형의 한계 값을 넘어버릴 수 있습니다. 이를 대처하기 위해선 제곱 수의 일의 자리의 특성을 알면 좋습니다. 제곱 수의 1의 자리는 4번 주기로 반복됩니다. 수학적으로 증명하기에는 너무 복잡하기에 "그렇구나" 정도로 알아두는 게 좋습니다. 이를 이용하면 문제에서 입력되는 b를 최소화할 수 있습니다. 코드 package main import ( "bufio" "f..

개요 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 우선 문제 이름처럼 DFS, BFS를 알아야 합니다. DFS (Depth-First Search), 깊이 우선 탐색 그래프의 모든 정점을 탐색하는 방법으로 최대한 깊이 탐색을 한 후 더 이상 깊이 들어가지 못한다면 이전으로 돌아와 다른 진행 방향으로 깊이 탐색을 진행합니다. 노드들을 돌며 순서를 스택(재귀)에 쌓는 방식을 사용합니다. 아래처럼 끝까지 가보..

개요 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2xn 직사가형을 2x1, 1x2 직사각형으로 채우기 문제입니다. 그림을 보면 매우 쉽게 풀 수 있던 문제입닌다. 일단 기본적으로 이전 거에서 1x2를 붙이는 것만으로 경우의 수가 어느 정도 정해졌습니다 그리고 또 알 수 있는 건 이전의 이전 거를 기준으로 2x2에 공간이 생겼는데 여기에도 2x1을 두개 넣은 2x2 정사각형을 붙임으로써 고유 경우의 수를 만들 수 있습니다 말로만 하면 그런가라는 생각이 들 수 있..

브루스 포스 브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)이라 불리는 알고리즘있습니다, 알고리즘이라고 칭하기도 애매하지만 알고리즘입니다. 바로 모든 경우의 수를 때려 박는 알고리즘입니다. 가장 완벽하며 가장 비효율적인 알고리즘이라고 할 수 있습니다 브루스 포스로 문제를 하나 풀었습니다. https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 처음에 흰색으로 시작할 때와 ..

개요 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 처음에는 1920번 수 찾기를 풀었던 경험을 살려 정렬 후 비교하는 로직의 방향으로 코드를 개발했습니다. 다음 규칙을 만족하면 비슷한 단어를 취급합니다 구성은 GOD와 DOG를 두고 각각의 알파뱃의 개수가 완전히 같은 경우를 말한다. 문자의 글자수가 같다면 안에 구성이 하나는 달라도 된다. 글자수 차이가 1개가 난다면 안의 구성이 하나는 달라도 된다. 비슷한 단어를 찾을 값과 비슷한 단어의..

개요 https://www.acmicpc.net/problem/7489 생각을 잘못해서 몇 번 틀린 문제입니다. 간단하게 팩토리얼 수에서 최우측의 0이 아닌 값을 출력하면 되는 문제인데 아 10보다 큰수는 10의 나머지로 계산하면 더 계산이 빨라지겠구나라는 생각을 하여 아래 코드를 넣은 게 실수였습니다. 왜냐하면 25같이 특정 수와 만나면 10의 제곱이 되는 수가 존재하기 때문에 함부로 나머지 연산을 사용하면 안되는 거였죠 if result > 10 { result = result % 10 } 코드 위와 비슷한 코드가 들어갑니다. 문제에서 언급했듯이 70!은 부동 소수점 변수의 위치까지 넘어가는 매우 큰 수 이므로 이를 처리해야 하는 코드가 필요합니다. 그래서 아래 코드를 넣었습니다, 이 코드도 수가 더..