알고리즘
-
BJ G4 19238 스타트택시 문제링크 http://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 M 명의 손님을 목적지로 이동시킴 따라서 M 번 손님 선택 --> 목적지 이동을 반복 손님 선택 기준: 1. 가장 가까운 위치의 손님 2. 1이 같다면 행 번호가 가장 작은 손님, 2도 같다면 열 번호가 가장 작은 손님 1칸을 이동할 ..
BJ G4 19238 스타트택시BJ G4 19238 스타트택시 문제링크 http://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 M 명의 손님을 목적지로 이동시킴 따라서 M 번 손님 선택 --> 목적지 이동을 반복 손님 선택 기준: 1. 가장 가까운 위치의 손님 2. 1이 같다면 행 번호가 가장 작은 손님, 2도 같다면 열 번호가 가장 작은 손님 1칸을 이동할 ..
2020.07.04 -
BJ G4 17142 연구소3 문제링크 http://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 전체 2로 표현되어있는 지점들의 개수를 K개라고 할 때 이중 M개를 순서 없이 활성화 시키므로 kCm의 조합을 찾는 것이 첫번째 임무 - 따라서 맵을 읽는 과정에서 바이러스 지점들의 목록을 만들어준다. - 또한 아직 오염되지 않은 지점 즉 0인 지점도 따로 관리한다. * 이제 선택..
BJ G4 17142 연구소3BJ G4 17142 연구소3 문제링크 http://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 전체 2로 표현되어있는 지점들의 개수를 K개라고 할 때 이중 M개를 순서 없이 활성화 시키므로 kCm의 조합을 찾는 것이 첫번째 임무 - 따라서 맵을 읽는 과정에서 바이러스 지점들의 목록을 만들어준다. - 또한 아직 오염되지 않은 지점 즉 0인 지점도 따로 관리한다. * 이제 선택..
2020.06.12 -
SWEA 모의 1963 탈주범 검거 문제링크 http://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 파이프 정보 - 파이프는 1~7까지 고정된 형태로 주어지며 들어가는 구멍과 나가는 구멍이 중요 - boolean[][] 형태에 열린 공간은 true로 설정 - 이때 방향은 북쪽을 0으로 해서 시계방향으로 맞춰야 나중에 사방탐색 할 때나 파이프간의 연결을 확인할 때 수월..
SWEA 모의 1963 탈주범 검거SWEA 모의 1963 탈주범 검거 문제링크 http://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 파이프 정보 - 파이프는 1~7까지 고정된 형태로 주어지며 들어가는 구멍과 나가는 구멍이 중요 - boolean[][] 형태에 열린 공간은 true로 설정 - 이때 방향은 북쪽을 0으로 해서 시계방향으로 맞춰야 나중에 사방탐색 할 때나 파이프간의 연결을 확인할 때 수월..
2020.06.08 -
BJ G5 17141 연구소2 문제링크 www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이�� www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 이차원 배열을 이용한 사방탐색 문제. 기본적으로는 BFS 기반의 완탐 처리 * 연구소 상태에서 2로 주어진 공간이 실제 바이러스가 놓인 곳이 아니라 놓을 곳이라는 점에 주의 - 2의 공간이 K개, 놓은 바이러스 개수가 m개 일 때 kCm을 구한 후 그 상황에서 각 바이러스를 기점으로 완탐 ..
BJ G5 17141 연구소2BJ G5 17141 연구소2 문제링크 www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이�� www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 이차원 배열을 이용한 사방탐색 문제. 기본적으로는 BFS 기반의 완탐 처리 * 연구소 상태에서 2로 주어진 공간이 실제 바이러스가 놓인 곳이 아니라 놓을 곳이라는 점에 주의 - 2의 공간이 K개, 놓은 바이러스 개수가 m개 일 때 kCm을 구한 후 그 상황에서 각 바이러스를 기점으로 완탐 ..
2020.06.01 -
SWEA D4 3234 준환이의 양팔저울 문제링크 www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 좀 더 치밀한 가지치기가 필요한 상황 * 1번 가지치기: 오른쪽의 무게가 왼쪽 보다 커서는 안된다. - 이건 쉽게 생각할 수 있고.. * 2번 가지치기: 추를 올리는 과정에서 현재까지 오..
SWEA D4 3234 준환이의 양팔 저울SWEA D4 3234 준환이의 양팔저울 문제링크 www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 좀 더 치밀한 가지치기가 필요한 상황 * 1번 가지치기: 오른쪽의 무게가 왼쪽 보다 커서는 안된다. - 이건 쉽게 생각할 수 있고.. * 2번 가지치기: 추를 올리는 과정에서 현재까지 오..
2020.05.31 -
BJ G4 1062 가르침 문제링크 http://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 어떤 알파벳을 배우느냐 배우지 않느냐의 선택 문제. 하지만 이들의 순서는 무관하기 때문에 조합적 문제 - 총 26개의 알파벳에서 K개를 골라야 한다. - 하지만 모든 단어는 anta로 시작하고 tica로 끝나기 때문에 a,n,t,i,c이 다섯 글자는 반드시 알아야 한다..
BJ G4 1062 가르침BJ G4 1062 가르침 문제링크 http://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 어떤 알파벳을 배우느냐 배우지 않느냐의 선택 문제. 하지만 이들의 순서는 무관하기 때문에 조합적 문제 - 총 26개의 알파벳에서 K개를 골라야 한다. - 하지만 모든 단어는 anta로 시작하고 tica로 끝나기 때문에 a,n,t,i,c이 다섯 글자는 반드시 알아야 한다..
2020.05.30 -
SWEA 모의 2105 디저트 카페 문제링크 http://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 [고려사항] 디저트 카페를 돌아다니며 디저트를 먹는데 이동 방향을 대각선이다. 이동 시 주의 사항이 여러가지 존재하는데 1. 어느 한 카페에서 출발한다 -- 어딘지 특정할 수 없기 때문에 모든 점에서 탐색 해볼 필요가 있다. 2. 대각선 방향으로 움직이고 사각형 모양을 그리..
SWEA 모의 2105 디저트 카페SWEA 모의 2105 디저트 카페 문제링크 http://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 [고려사항] 디저트 카페를 돌아다니며 디저트를 먹는데 이동 방향을 대각선이다. 이동 시 주의 사항이 여러가지 존재하는데 1. 어느 한 카페에서 출발한다 -- 어딘지 특정할 수 없기 때문에 모든 점에서 탐색 해볼 필요가 있다. 2. 대각선 방향으로 움직이고 사각형 모양을 그리..
2020.05.29 -
BJ G4 1277 발전소 설치 문제링크 http://www.acmicpc.net/problem/1277 1277번: 발전소 설치 문제 엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 최종적으로 연결해야 할 것은 1번 발전소에서 맨 마지막 N 번 발전소 -- 이때 발전소 간의 가중치가 있기 때문에 dijkstra 알고리즘을 사용해보자. * 그래프 구성 -- 정점인 발전소의 개수가 1000개로 크지 않으므로 인접 행렬로 처리해도 무방함 -- 거리 기준으로 ..
BJ G4 1277 발전소 설치BJ G4 1277 발전소 설치 문제링크 http://www.acmicpc.net/problem/1277 1277번: 발전소 설치 문제 엄청난 벼락을 맞아 많은 전선들이 끊어져 현재 전력 공급이 중단된 상태이다. 가장 심각한 문제는 1번 발전소에서 N번 발전소로 가는 중간의 전선이 끊어진 것이기에 일단 이 두 발전소를 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 최종적으로 연결해야 할 것은 1번 발전소에서 맨 마지막 N 번 발전소 -- 이때 발전소 간의 가중치가 있기 때문에 dijkstra 알고리즘을 사용해보자. * 그래프 구성 -- 정점인 발전소의 개수가 1000개로 크지 않으므로 인접 행렬로 처리해도 무방함 -- 거리 기준으로 ..
2020.05.28