거의 알고리즘 일기장

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 풀이방법 1. cctv를 기준으로 left, right, up, down을 채울수 있는 함수 4개를 만든다. (밑의 코드참조) void f..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이방법 이 문제도 그냥 시뮬레이션 문제다. 그러므로 주의사항을 보고 꼼꼼히만 코딩을 완성하기만 하면 어렵지않다. 한가지만 주의하자 1. 이미 돌렸던 기어는 다시 돌리면 안된다. 재귀문을 짤때 이 부분을 넣어주지 않으면 재귀문이 끝나지 않을 수 있다. 전체코드 #include #include #include #include using namespace std; int Gears[4][8]; v..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 1. 1 방향으로 한번, 2 방향으로 한번 완전탐색을 돌린다. 2. 탐색하며 바꿔야 할것 2.1 옆에 값과 현재 값이 같을때 -> 그냥 통과 2.2 옆에 값과 현재 값이 다를때 2.2.1 옆에 값과 현재 값의 차이가 1이하일때 2.2.1.1 현재 값 > 옆의 값 2.2.1.1.1 visited 에 걸릴때 -> 이 줄은 안됨 2.2.1.1.2 안걸릴때 2.2.1.2 현재 값 < 옆의 값 ...위와 동일 2.2.2..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이방법 이 문제도 조합을 이용하면 매우매우 간단하다. 1. 조합을 이용해서 팀1, 팀2로 나눈다 2. 나눈 팀의 스코어를 계산한다. 3. 절대값(팀1 -팀2)과 저장된 값과 최솟값을 비교한다. 4. 모든 조합이 나올때까지 반복 (만약 지금 저장된 값이 0이면 0보다 최솟값은 없으므로 break해도됨) #include #include #include #define LIMIT 987654321 using namespac..

https://www.algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자 www.algospot.com 풀이방법 1. * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 2. ? 는..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 주의할점 1. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 2. 나눗셈은 정수 나눗셈으로 몫만 취한다. 풀이방법 c++을 이용한다면 next_permutation함수를 쓰면 간단하다. 나는 c++을 사용하므로 이 방법에 대해서 설명하겠다. 1. 덧셈(0), 뺄셈(1), 곱셈(..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이방법 그냥 주어진 이 조건들을 만족하는 dfs를 만들면된다. 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준..

https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다. 균형을 잃어서 다른 발로 서거 algospot.com 풀이방법 이 문제는 시간 : 3초, 테스트케이스 : 최대 50개, n : 최대 100 의 조건이 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 풀이방법 기본적인 다익스트라 알고리즘을 사용하면 풀린다. 전체코드 #include #include #include #include..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 풀이방법 그냥 유니온 파인드 알고리즘 이용하면 답 나옴(밑의 url참조) https://kunkunwoo.tistory.com/22 백..