2차원 배열에서 패턴 찾기 Jaekwan 안녕하세요. 2차원 배열에서 패턴을 찾는 문제에서 고민하다가 속도가 느려서 질문을 올립니다. 문제: 주어진 2차원 배열에서 특정 패턴의 빈도수를 계산하여라.(최고 1000x1000 배열) 패턴: + 모양의 패턴 예 : 주어진 5x5 배열에서 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 결과 : 2개 ( 큰 +, 작은 +) 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 예외: 단 +자 모양에서 단 한 개만 0인 경우도 찾은 결과로 인식한다. 따라서, 아래 모양도 성립한다. 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 배열을 순회하면서 각 셀에서 점점 영역을 넓혀 가는 방법으로 검색을 하였는데 결과는 찾았지만, 속도가 너무 느리네요. 다른 방법의 검색방법이 있을까요? 9년 전
2개의 댓글이 있습니다. Jaekwan 문제 해결 했습니다. 큰 십자의 경우가 해당된다면, 그보다 작은 경우의 십자는 무조건 해당되므로, 각 셀에서 해당되는 가장 큰 십자를 찾는 문제였네요. 이분법으로 가장 큰 십자를 찾는 법으로 해결하였습니다. 9년 전 link Being 잘 해결하셨네요. 어떻게 이분법을 활용하셨는지는 모르겠지만 중심에서 상하좌우로 개수를 세셨다면 어차피 세던 것을 반복해서 세던 것이라 이분법이 의미가 없는 것 같습니다. 덧붙이자면 가장 빠른 방법은 추가 메모리를 사용한 동적 계획법을 떠올릴 수 있겠네요. 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Jaekwan
안녕하세요. 2차원 배열에서 패턴을 찾는 문제에서 고민하다가 속도가 느려서 질문을 올립니다.
문제: 주어진 2차원 배열에서 특정 패턴의 빈도수를 계산하여라.(최고 1000x1000 배열)
패턴: + 모양의 패턴
예 :
주어진 5x5 배열에서
0 0 1 0 0
0 1 1 0 1
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
결과 : 2개 ( 큰 +, 작은 +)
0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
예외: 단 +자 모양에서 단 한 개만 0인 경우도 찾은 결과로 인식한다.
따라서, 아래 모양도 성립한다.
0 0 0 0 0
0 0 1 0 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0
배열을 순회하면서 각 셀에서 점점 영역을 넓혀 가는 방법으로 검색을 하였는데 결과는 찾았지만, 속도가 너무 느리네요. 다른 방법의 검색방법이 있을까요?
9년 전