문자열 검색 알고리즘 - KMP 알고리즘 바로가기 ● 1. 보이어-무어 알고리즘(Boyer-Moore algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 것으로, 이전 포스팅에서 살펴본 KMP 알고리즘의 목적과 유사합니다. 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것이 주 목표입니다. 보이어-무어 알고리즘은 보통 상황에서 ...
알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘
＠ 문자열을 검색하려면? : 패턴 매칭 문자열을 검색하는 상황은 많은 상황에서 쓰입니다. 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 ctrl+F 를 눌러서 검색하는 데에도 사용될 수 있습니다. 이렇듯 본문이 되는 String에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니...
알고리즘 - 1211. [S/W 문제해결 기본] 사다리타기 문제(2)
SW Expert Academy 의 1211번 문제입니다. 사다리 타기 문제 1과 유사하나, 구해야 하는 결과가 다릅니다. 100x100 의 2차원 배열에 사다리로 탈 수 있는 길이 ‘1’로 표시되고, 그렇지 않은 곳은 ‘0’으로 표시되어 input이 주어집니다. 시작점에서 끝점까지 나갈 수 있는 모든 경로들 중 가장 짧은 경로를 갖는 시작점의 ...
알고리즘 - 1210. [S/W 문제해결 기본] 사다리타기 문제(1)
SW Expert Academy 의 1210번 문제입니다. 사다리 타기 문제입니다. 100x100 의 2차원 배열에 사다리로 탈 수 있는 길이 ‘1’로 표시되고, 그렇지 않은 곳은 ‘0’으로 표시되어 input이 주어집니다. 맨 마지막 출구는 배열에 ‘2’로 표시되어 있으며, 출구로 나갈 수 있는 출발점의 열 번호를 출력하는 문제입니다. 조건문...
알고리즘 - 1209. [S/W 문제해결 기본] Sum 문제
SW Expert Academy 의 1209번 문제입니다. 100x100 의 2차원 배열이 주어지고, 각 행 및 열들의 데이터 합과 두 대각선 데이터의 합들 중 최댓값을 찾는 문제로 아주 단순한 문제입니다. 난이도 : 1 문제 조건 배열의 크기는 100x100 이다. 각 행 혹은 열, 대각선 데이터의 ...
알고리즘 - 순차 검색과 이진 검색, 인덱스
SW Expert Academy 의 SW문제해결 기본 Array 2 강좌 - 3차시 주제입니다. 검색은 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업, 즉 목적하는 탐색키를 가진 항목을 찾는 것이라 할 수 있습니다. 검색의 종류에는 순차 검색, 이진 검색, 인덱싱 등이 있습니다. 순차 검색 순차 검색은 말 그대로 일렬로 되어 있...
알고리즘 - 부분집합과 그 합 알고리즘
SW Expert Academy 의 SW문제해결 기본 Array 2 강좌 - 2차시 주제입니다. 부분집합의 합 문제 - 모든 부분집합을 생성하는 방법 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내야 하는 문제입니다. 완전 검색 기법(Exhaustiv...
알고리즘 - 1208. [S/W 문제해결 기본] Flatten 문제
SW Expert Academy 의 1208번 문제입니다. 벽면에 가장 높이 쌓여진 상자의 한 칸을, 가장 낮게 쌓인 상자 위에 옮기는 ‘덤프’ 작업을 반복합니다. 이렇게 최고점과 최저점의 간격을 줄이는 작업을 평탄화(Flatten)이라고 합니다. 제한된 덤프 횟수 내에서 평탄화를 진행한 뒤 최고점-최저점의 높이차를 구합니다. 난이도 : 1...
알고리즘 - 1206. [S/W 문제해결 기본] View 문제
SW Expert Academy 의 1206번 문제입니다. 건물이 옆으로 밀집한 공간에서 각 층마다 조망권을 확보해야 합니다. 이 때 조망권은, 각 층에서 최소한 두 칸 이내에는 다른 건물이 없어야 보장된다고 말합니다. (즉, 양 옆에 두 칸 이상의 공백이 존재해야 한다는 말) 난이도 : 1 문제 조건 가로 길이는 100...
알고리즘 - 1204. [S/W 문제해결 기본] 최빈수 찾기 문제
SW Expert Academy 의 1204번 문제입니다. [S/W 문제해결 기본] 강좌를 수강하시는 분들이라면 가장 처음 만날 수 있는 문제입니다. 난이도 : 1 Input 첫 줄에는 테스트 케이스 T가 주어지고, 그 다음줄에는 각 테스트 케이스의 번호가 주어지며, 그 다음줄부터는 1000개의 학생 점수 데이터(0점부터 100점까지의 범...