우대비의 블로그

10816번: 숫자 카드 2 들어가며이 문제는 숫자 카드를 몇개 가지고 있는지 찾는 문제입니다. 상근이가 가지고있는 숫자 카드의 최대 개수는 50만개,체크 해야할 숫자 카드의 최대 개수가 50만개이기 때문에 2중 for문을 사용하면 시간 초과가 발생합니다. 가장 빠르게 풀 수 있는 방법은 Dictionary를 통해 상근이가 가지고 있는 숫자 카드의 개수를 저장하는 것입니다.Dictionary cards = new Dictionary();cards[숫자 카드] += 1; 하지만, 해당 문제는 이진 탐색 문제이기에 이진 탐색 풀이 방법을 공유하겠습니다. 풀이 방법이진 탐색을 통해 상근이가 가지고 있는 숫자를 찾기 위해서는 우선, 상근이의 카드를 정렬 해줘야합니다.정렬된 카드들을 이진 탐색을 통해 위치를 ..

풀이 방법해당 문제는 완전 탐색을 통해 풀이해야 합니다.모든 경우의 수를 하나하나 탐색하여 퀸을 놓을 수 있는지 체크하고, 개수를 저장하고 출력하면 됩니다. 힌트 1퀸은 상, 하, 좌, 우로 이동할 수 있습니다.즉, 현재 놓으려는 위치의 Y값과, X값을 사용하는 다른 퀸이 존재한다면, 그 자리는 놓을 수 없는 자리입니다.그렇기에 Y값 하나에 1개씩, X값 하나에 1개씩 밖에 퀸을 둘 수가 없습니다. 힌트 2퀸은 대각선으로도 이동할 수 있습니다.즉 퀸A에 퀸B의 위치값을 뺄 때, 방향 벡터 X와 Y의 절대값이 같다면 대각선에 위치한다는 의미이기 때문에놓을 수 없는 경우의 수 입니다. 힌트 3최대 15개의 퀸을 15 * 15개의 체스판에 모두 배치하는 모든 경우의 수를 탐색할 때,반복문을 어떻게 배치해야할지..

using System;using System.Collections.Generic;using System.Linq;namespace Alroghtim_CS{ class Program { static void Input(out List rank, out List newRanks) { rank = new List(); newRanks = new List(); int n = int.Parse(Console.ReadLine()); string[] ranking = Console.ReadLine().Split(' '); for (int i = 0; i rank, out List newRanks); int n = rank.Count; HashSet[] outDegree = new Ha..

11729번: 하노이 탑 이동 순서 문제세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다. 풀이 방법힌트1가장 아래의 원판을 3번째로 옮기려면 어떻게 해야할까?당연하게도 다른 모든 원판을 2번째로 옮겨야 한다. 즉, 가장 큰 원판을 제외한 다른 원판을 중간 지점으로 보내는 것이 핵심이..

9663번: N-Queen (acmicpc.net) N * N크기의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓을 수 있는 경우의 수를 찾는 문제입니다. 풀이 방법경우의 수를 찾는 문제여서 점화식을 구하는 문제라 생각할 수도 있습니다만시간제한이 10초인 것을 보면 브루트포스 알고리즘이라는 것을 알 수 있겠습니다. 이 문제를 풀기 위해서는 퀸을 놓을 수 없는 위치의 조건을 생각해볼 필요가 있습니다.퀸은 8개의 방향으로 원하는 만큼 이동할 수 있습니다.즉 같은 x선에 있으면 안되고 같은 y선에 위치하면 안됩니다.또한 대각선 방향도 위치할 수 없습니다. // (상 하 좌 우) 방향if (dir.x * dir.y == 0) return false;// 대각 방향if (abs(dir.x) - a..

11758 CCW (기하학) [Gold V]11758번: CCW (acmicpc.net) 이 문제는 CCW(Counter-Clockwise) 공식을 알고있는지 물어보는 문제입니다.이 공식을 이용하면 시계 반대방향으로 회전하는지 확인할 수 있습니다. CCW 공식은 아래와 같습니다.flrjtwjrjt.tistory.com  17387 선분 교차 2(기하학) [Gold II]17387번: 선분 교차 2 (acmicpc.net)  11758 CCW (기하학) [Gold V]11758번: CCW (acmicpc.net) 이 문제는 CCW(Counter-Clockwise) 공식을 알고있는지 물어보는 문제입니다.이 공식을 이용하면 시계 반대방향으로 회전하flrjtwjrjt.tistory.com 선분 교차2 문제와 굉..

17387번: 선분 교차 2 (acmicpc.net)  11758 CCW (기하학) [Gold V]11758번: CCW (acmicpc.net) 이 문제는 CCW(Counter-Clockwise) 공식을 알고있는지 물어보는 문제입니다.이 공식을 이용하면 시계 반대방향으로 회전하는지 확인할 수 있습니다. CCW 공식은 아래와 같습니다.flrjtwjrjt.tistory.com 두개의 점(x,y)으로 만들어진 선을 두개 입력 받아서두 선이 교차 하는지 아닌지 체크하는 문제입니다.CCW를 이용하면 쉽게 풀 수 있습니다. 풀이법두 개의 선이 만약 교차 할 때의 경우를 생각해보겠습니다.선 ㄱ과 ㄴ이 있다고 가정하고 ㄱ은 두개의 벡터 A, B ㄴ은 C, D로 이루어져 있다고 가정하겠습니다. ㄱ과 ㄴ이 교차하는 상황에..

11758번: CCW (acmicpc.net) 이 문제는 CCW(Counter-Clockwise) 공식을 알고있는지 물어보는 문제입니다.이 공식을 이용하면 시계 반대방향으로 회전하는지 확인할 수 있습니다. CCW 공식은 아래와 같습니다.CCW = (A.x*B.y + B.x*C.y + C.x*A.y) - (A.x*C.y + B.x*A.y + C.x*B.y) A, B 벡터를 기준으로 C벡터가 왼쪽 방향에 위치한지 오른쪽 방향에 위치한지 알 수 있으며시계 방향일 경우 0보다 작은 값이 나오고반시계 일 경우에는 0보다 큰 값이 나옵니다.세 벡터가 일직선에 놓인 경우에는 결과값으로 0이 나옵니다. 풀이법11758번 문제는 3개의 벡터 x,y값을 입력받고시계 방향을 나타내면 1, 반시계는 -1, 일직선을 0을 출력..

11049번: 행렬 곱셈 순서 (acmicpc.net) 동적 계획법2747번: 피보나치 수 (acmicpc.net) 피보나치는 수는 0과 1로 시작하며 2번째 부터는 앞의 두 수를 더해서 이어 나갑니다.즉 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 --------으로 이어집니다. N번째 피보나치 수flrjtwjrjt.tistory.com N개의 행렬을 곱하는 순서를 다르게 하여 가장 적은 곱셈 연산수를 찾는 문제입니다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이..

1915번: 가장 큰 정사각형 (acmicpc.net) n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.0100011111100010위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.  풀이법 최대한 적은 양의 연산으로 안이 꽉 채워진 정사각형을 찾아야 합니다. 여기서 핵심은 꽉 채워진 정사각형은 결국 작은 정사각형의 모임이라는 것 입니다.  위의 3*3 정사각형 안에도 4개의 2*2 정사각형이 보이네요마찬가지로 4 * 4 정사각형도 4개의 3 * 3 정사각형이 보이겠죠? 그럼 2 * 2 정사각형은 어떻게 정의 될까요?왼쪽, 위, 대각선 방향의 인덱스에 1이 입력이 되어 있다면 2 * 2 정사각형 이라고 할 수 있겠습니다...