Algorithms, Data Analytics

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

pro = input()
target = input()
count = 0
i = 0

while len(pro) - i >= len(target):
    
    if pro[i : (i + len(target))] == target:
        count += 1
        i += len(target)
        
    else:
        i += 1
        
print(count)

처음에는 for문으로 해결해보려다가 i 값을 일정하게 증가시키는 것이 아닌 조건에 맞게 조정을 하는 것이 필요해서 

while문을 쓰게 되었다.

그러니 문제가 생각보다 빨리 풀림.

알고리즘은 이런 생각의 전환이 빨리빨리 되는 것이 중요한듯하다.

안될 것 같으면 빠르게 다른 방법을 생각하는..

물론 처음부터 좋은 방법이 생각나는게 가장 좋겠지만

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

def solve(n, x, y):
    global cnt
    if n == 2:
        if (x == r and y == c):
            print(cnt)
            return
        cnt += 1
        
        if (x == r and y + 1 == c):
            print(cnt)
            return
        cnt += 1
        
        if (x + 1 == r and y == c):
            print(cnt)
            return
        cnt += 1
        
        if (x + 1 == r and y + 1 == c):
            print(cnt)
            return
        cnt += 1
        return
    
    solve(n / 2, x, y)
    solve(n / 2, x, y + (n / 2))
    solve(n / 2, x + (n / 2), y )
    solve(n / 2, x + (n / 2), y + (n / 2))
    
N, r, c = map(int, input().split())
cnt = 0
solve(2 ** N, 0, 0)

문제 이해는 했는데 어떻게 구현해야 할지 감이 안와서

강의를 먼저 봤다.

전에는 몰랐던 global 변수선언과 재귀적으로 파트를 나눠서 접근하는 방식에 대해 조금은... 이해가 갔다

알고리즘적 사고가 느는건지 문제 푸는 방법을 아는건지 헷갈린다 ㅋㅋㅋㅋ

문제

영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.

출력

첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.

n, m = map(int, input().split())
castle = []
row = [0] * n
column = [0] * m
row_count = 0
column_count = 0

for _ in range(n):
    castle.append(input())
    
for i in range(n):
    
    for j in range(m):
        
        if castle[i][j] == 'X':
            row[i] = 1
            column[j] = 1
            
for i in range(n):
    if row[i] == 0:
        row_count += 1
        
for j in range(m):
    if column[j] == 0:
        column_count += 1

print(max(row_count, column_count))

오랜만에 올린다.

머리로는 이해하겠는데 ㅋㅋㅋㅋㅋ역시나 표현이 어렵다.

처음에 한번에 코드를 짜려고 하니까 그런 것 같다.

막상 답을 보면 어렵진 않은데

차근차근 하나씩 짜보려고 해야겠다.