알고리즘
-
SWEA 모의 5653 줄기세포 배양 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=uITWSBp2RUw&t=476s 소스..
SWEA 모의 5653 줄기세포 배양SWEA 모의 5653 줄기세포 배양 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo&categoryId=AWXRJ8EKe48DFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=uITWSBp2RUw&t=476s 소스..
2020.04.29 -
BOJ S3 6987 월드컵 문제링크 https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=O0G5QrCMAhE&feature=youtu.be 소스 보기 동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요. 더보기 package bj.silver.l3; import java.io.BufferedReade..
BJ S3 6987 월드컵BOJ S3 6987 월드컵 문제링크 https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=O0G5QrCMAhE&feature=youtu.be 소스 보기 동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요. 더보기 package bj.silver.l3; import java.io.BufferedReade..
2020.04.29 -
BJ G3 2146 다리만들기 문제링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고..
BJ G3 2146 다리만들기BJ G3 2146 다리만들기 문제링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고..
2020.04.28 -
BJ G3 17472 다리 만들기 2 문제링크 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=Vop0L7vU1-0 소스 보기 동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다...
BJ G3 17472 다리 만들기 2BJ G3 17472 다리 만들기 2 문제링크 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=Vop0L7vU1-0 소스 보기 동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다...
2020.04.27 -
SWEA D4 4366 정식이의 은행업무 문제링크 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMeRLz6kC0DFAXd&categoryId=AWMeRLz6kC0DFAXd&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/bgcK6abgbwk 소스 보기 동영상 설명을 보..
SWEA D4 4366 정식이의 은행업무SWEA D4 4366 정식이의 은행업무 문제링크 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMeRLz6kC0DFAXd&categoryId=AWMeRLz6kC0DFAXd&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/bgcK6abgbwk 소스 보기 동영상 설명을 보..
2020.04.27 -
BJ G5 15686 치킨배달 문제링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 용어..
BJ G5 15686 치킨배달BJ G5 15686 치킨배달 문제링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 용어..
2020.04.26 -
SWEA 모의 2117 홈방범서비스 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 서비스는 센터를 중심으로 마름모 형태로 운영됨 * 서비스는 운영 비용이 발생: 비용은 서비스 영역의 면적과 동일 -- 운영 비용 = K * K + (K - 1) * (K - 1) --> 이 비용은 면적에 따라 동일하기 때문에 탐색 하기 전에 미리 구해놓자!! -- 주..
SWEA 모의 2117 홈방범서비스SWEA 모의 2117 홈방범서비스 문제링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 핵심 컨셉 고려사항 * 서비스는 센터를 중심으로 마름모 형태로 운영됨 * 서비스는 운영 비용이 발생: 비용은 서비스 영역의 면적과 동일 -- 운영 비용 = K * K + (K - 1) * (K - 1) --> 이 비용은 면적에 따라 동일하기 때문에 탐색 하기 전에 미리 구해놓자!! -- 주..
2020.04.25 -
* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다. 다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는 KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다. Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다. KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치..
문자열 패턴 매칭 3 - KMP* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다. 다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는 KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다. Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다. KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치..
2020.02.28