알고리즘
-
Michael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다. 매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다. 해쉬값의 생성 해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 패턴의 해쉬값은 당연히 고정되어있다. 비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다. 이를 위해 패턴은 통상 아래 수식으로 계산된다. ..
문자열 패턴 매칭 2 - Rabin KarpMichael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다. 매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다. 해쉬값의 생성 해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 패턴의 해쉬값은 당연히 고정되어있다. 비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다. 이를 위해 패턴은 통상 아래 수식으로 계산된다. ..
2020.02.28 -
워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
문자열 패턴 매칭 1 - Brute Force워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
2020.02.28 -
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=407&sca=40 JUNGOL | 맛있는 음식(PERKET) > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 308 회 시도횟수: 639 회 "퍼킷"은 널리 알려진 맛있는 음식이다. 퍼킷이 맛있는 음식으로 전통을 유지할 수 있던 이유는 요리사들이 "퍼킷"의 맛을 위해 재료를 고르는데 있어 신중했기 때문이다. 여러분에게 N개의 재료가 주어진다. S는 신맛을 B는 쓴맛을 뜻한다고 하자. 다양한 재료가 쓰인다고 할 때, 신맛의 합은 우리가 선택한 각 신맛재료의 신맛 지수들을 곱한 값이고 www.jungol.co.kr 재료가 조합될 수 있는 모든 경우의 수를 완탐해보고 최소값을 구해..
1127 : 맛있는 음식(PERKET)http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=407&sca=40 JUNGOL | 맛있는 음식(PERKET) > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 308 회 시도횟수: 639 회 "퍼킷"은 널리 알려진 맛있는 음식이다. 퍼킷이 맛있는 음식으로 전통을 유지할 수 있던 이유는 요리사들이 "퍼킷"의 맛을 위해 재료를 고르는데 있어 신중했기 때문이다. 여러분에게 N개의 재료가 주어진다. S는 신맛을 B는 쓴맛을 뜻한다고 하자. 다양한 재료가 쓰인다고 할 때, 신맛의 합은 우리가 선택한 각 신맛재료의 신맛 지수들을 곱한 값이고 www.jungol.co.kr 재료가 조합될 수 있는 모든 경우의 수를 완탐해보고 최소값을 구해..
2019.08.15 -
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 아마도 입력 데이터에 문제가 있는듯하다. BufferedReader를 사용하면 runtime 오류 발생 --> 반드시 Scanner 사용할 것 public class Solution { static Scanner scanner = new Scanner(System.in); static StringBuilder sb; static StringTokenizer tokens; static ..
4796. 의석이의 우뚝 선 산https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 아마도 입력 데이터에 문제가 있는듯하다. BufferedReader를 사용하면 runtime 오류 발생 --> 반드시 Scanner 사용할 것 public class Solution { static Scanner scanner = new Scanner(System.in); static StringBuilder sb; static StringTokenizer tokens; static ..
2019.08.08 -
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1006&sca=2040 JUNGOL | 오목 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1262 회 시도횟수: 7135 회 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 www.jungol.co.kr 속도는 좀 빨라졌는데 많이 너저분해진 코드 문제 해석시 약간의 오해가 있을 수 ..
1733 : 오목http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1006&sca=2040 JUNGOL | 오목 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1262 회 시도횟수: 7135 회 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 www.jungol.co.kr 속도는 좀 빨라졌는데 많이 너저분해진 코드 문제 해석시 약간의 오해가 있을 수 ..
2019.08.08 -
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=50&sfl=wr_hit&stx=1809&sop=and JUNGOL | 탑 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1866 회 시도횟수: 7872 회 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고 www.jungol.co.kr 카테고리는 stack이라고 되어있..
1809 : 탑http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=50&sfl=wr_hit&stx=1809&sop=and JUNGOL | 탑 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1866 회 시도횟수: 7872 회 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고 www.jungol.co.kr 카테고리는 stack이라고 되어있..
2019.08.08 -
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLL7kaaAPsDFAUW&categoryId=AWLL7kaaAPsDFAUW&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StringReader; import java.util.HashMap; import java.util.Map; ..
4261. 빠른 휴대전화 키패드https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLL7kaaAPsDFAUW&categoryId=AWLL7kaaAPsDFAUW&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StringReader; import java.util.HashMap; import java.util.Map; ..
2019.08.05 -
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StringReader; import java.util.StringTokenizer; // TODO: ht..
1824. 혁진이의 프로그램 검증https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StringReader; import java.util.StringTokenizer; // TODO: ht..
2019.08.02