AndroidTeacher

https://www.acmicpc.net/problem/16139

문제 설명

특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면

S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하자.

문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다.

풀이 과정

이 문제는 누적 합 으로 풀어야 시간초과 없이 해결할 수 있다.

만약, 매번 l부터 r까지 모든 문자를 돌며 개수를 카운트하는식으로 하여

N번 계산한다면 시간초과 오류가 발생하기 때문에

누적합을 이용해야 한다.

즉, 누적해서 횟수를 쌓아가야 한다는 뜻이다.

예를 들어 kakaotistory 라는 문자열이 있고, k가 들어가는 횟수를 센다고 할때,

k가 등장하지 않는 인덱스에는

k[5] = k[4]

k[6] = k[5] 

...

처럼 그 전 인덱스의 횟수를 그대로 쌓아가고

k 문자가 나타날 때는 그 인덱스에 +1을 추가해주어 누적해서 쌓아가면 된다.

kakaotistory 같은 경우 k가 0번째와 2번째에 나타나기 때문에k[0] = 1, k[1] = 1, k[2] = 2 ... k[11] = 2 이런식으로 쌓아가면 된다.

이렇게 알파벳마다 누적합 횟수를 저장해놓으면,

0번째부터 6번째 문자 사이에 k가 몇개 들어있는지 알아보아야 할 때,

매번 카운트 할 필요 없이

k[6] - k[0] 의 값을 구해서 바로 횟수를 구할 수 있기 때문이다.

그래서, 가장 먼저 문자열을 입력받고 나서

a~z별로 누적합을 먼저 저장해놓고

매 질문이 들어올때는 저장해놓은 누적합의 계산을 통해서 바로 답을 구하면 된다.

이를 파이썬으로 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
s = list(input().rstrip())
n = int(input().rstrip())

cList = [[0] * len(s) for _ in range(26)]

for i in range(len(s)):
  cList[ord(s[i])-ord('a')][i] += 1

for i in range(26):
  for j in range(1, len(s)):
    cList[i][j] += cList[i][j-1]

for i in range(n):
  a, l, r = input().split()
  tmp = cList[ord(a)-ord('a')][int(r)] - cList[ord(a)-ord('a')][int(l)]

  if s[int(l)] == a:
    tmp+=1
    
  print(tmp)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/2559

문제 설명

그림과 함께 제공되는 문제이니 자세한 문제설명은 위 링크를 참조해주세요.

풀이 과정

이 문제는 누적 합 으로 푸는 문제이다.

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류가 나게 된다.

그래서 매번 구간합을 구하는 것이 아니라,

처음에 n개의 수를 입력받고 나면

길이 n짜리 리스트를 만들어 리스트의 각 자리에 그 자리까지의 누적합을 저장한 후에

각 자리의 누적합에서 빼주는 방식으로 구간합을 구하면 된다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
pre = [0]
tmp_sum = []
mysum = 0

for i in range(n):
  mysum += nums[i]
  pre.append(mysum)


for i in range(n-m+1):
  tmp_sum.append(pre[i+m] - pre[i])

print(max(tmp_sum))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/11659

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

풀이 과정

이 문제는 

누적 합 으로 푸는 문제이다.

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류가 나게 된다.

그래서 매번 구간합을 구하는 것이 아니라,

처음에 n개의 수를 입력받고 나면

길이 n짜리 리스트를 만들어 리스트의 각 자리에 그 자리까지의 누적합을 저장한 후에

각 자리의 누적합에서 빼주는 방식으로 구간합을 구하면 된다.

예를 들어 2 ~ 4 구간합을 구한다면

4까지의 구간합에 2 이전 까지의 구간합을 빼면 되는 것이다.

이 때, 주의해야 할 점은

2 ~ 4 구간합이라고 하면 4까지의 구간합에 2 이전까지의 구간합이므로

맨 처음 리스트에 0을 넣어 인덱스를 맞춰주어야 한다.

맨 앞에 0을 붙여주자.

이를 파이썬코드로 나타내면 다음과 같다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
pre = [0]
mysum = 0

for i in range(n):
  mysum += nums[i]
  pre.append(mysum)


for i in range(m):
  a, b = map(int, input().split())
  print(pre[b] - pre[a-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/17478

문제 설명

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.

매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.

중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.

떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.

JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.

풀이 과정

이 문제는 재귀 구현 문제이다.

코드에 작성해야 하는 문자열은 위 링크의 예시답변을 참고해서 작성해야 한다.

예시답변의 구조를 보면 알 수 있듯이

마지막 "라고 답변하였지." 부분이 n의 개수에 맞춰 마지막에 한 번에 등장하는걸로 보아

질문과 답변 사이에 재귀로 동작해야 정상적으로 출력됨을 알 수 있다.

이를 고려한 파이썬 코드는 다음과 같다.

n = int(input())

print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
a = "____"

def recursive(cnt):
  question1(cnt)
  if cnt == n:
    answer2(cnt)
    answer3(cnt)
    return
    
  answer1(cnt)
  recursive(cnt+1)
  answer3(cnt)
  
def question1(cnt):
  print(a*cnt + "\"재귀함수가 뭔가요?\"")
  return

def answer1(cnt):
  print(a*cnt + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.")
  print(a*cnt + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
  print(a*cnt + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"")
  return

def answer2(cnt):
  print(a*cnt + "\"재귀함수는 자기 자신을 호출하는 함수라네\"")
  return

def answer3(cnt):
  print(a*cnt + "라고 답변하였지.")
  return

recursive(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/start/

문제 설명

A:1, C:2, G:3, T:4 이며 'A,C,G,T'로 이루어진 문자열 S를 P[i]부터 Q[i]까지 범위의 인덱스로 잘랐을 때

해당 문자열 내의 최솟값을 구하는 문제이다.

즉, 'CAGCCTA' 라는 문자열 S가 주어지고, P[0] = 2, Q[0] = 4 이면

자른 문자열은 GCC가 되고 여기서 최솟값은 C = 2가 된다.

풀이 과정

이 문제를 풀면서 굉장히 의아한 부분이 있다.

먼저, 문제의 의도는 Prefix Sum을 이용하는 문제이지만, 파이썬으로 풀었을 때 굉장히 간단한 방법으로 다음과 같이 풀어보았다.

[파이썬 코드]

def solution(S, P, Q):
    arr = []
    for i in range(len(P)):
        A = P[i]
        B = Q[i]
        tmp = S[A:B+1]

        if 'A' in tmp:
            arr.append(1)
        elif 'C' in tmp:
            arr.append(2)
        elif 'G' in tmp:
            arr.append(3)
        else:
            arr.append(4)
        
    return arr

이 코드로 시간복잡도가 O(N+M)이 나오며 효율성까지 100% 통과하며 만점을 받았다.

이 코드를 코틀린으로 변환하면 다음과 같다.

[코틀린 코드]

fun solution(S: String, P: IntArray, Q: IntArray): IntArray {
    val arr = IntArray(P.size){0}
    for(i in P.indices) {
        val tmp = S.substring(P[i], Q[i]+1)
        if(tmp.contains('A')) {
            arr[i] = 1
        } else if(tmp.contains('C')) {
            arr[i] = 2
        } else if(tmp.contains('G')) {
            arr[i] = 3
        } else {
            arr[i] = 4
        }
    }

    return arr
}

하지만 코틀린 코드는 시간복잡도 O(N*M)이 나오며 효율성에서 통과하지 못했다.

두 코드를 단순 비교했을 때는 분명히 같은 코드이며

둘다 O(N*M)으로 작동하는 것이 맞지만

왜 파이썬은 O(N+M)이 나오고, 파이썬만 통과하는지 이해가 되지 않는다.

전체 문자열의 길이만큼 for문을 돌기 때문에 N이 발생하고

그 안에서 파이썬은 in(O(N)), 코틀린은 contains(O(N)) 이 발생하기 때문에

결국엔 O(N*M)이 발생하는 것이 맞는 것 같은데...왜 파이썬만 O(N+M)으로써 통과되는지 모르겠다...

(혹시 아시는분이 계시다면 댓글 부탁드리겠습니다.)

단순히 언어의 작동방식 차이인지...아직까지 해결을 하지 못했다 ...

일단은 prefix sum을 이용하지 않는 방식으로 해결을 하였고

prefix sum으로 다시 풀어본 뒤 재 업로드를 하려고 한다.

https://www.acmicpc.net/problem/20057

문제 설명

문제의 자세한 설명은 위 링크를 참조하시길 바랍니다.

이 문제는 구현 시뮬레이션 문제로, 문제에서 요구하는 사항이 꽤 많고 상세합니다. 

빠짐없이 체크하여 어떻게 구현해야 할지 구상한 후에 구현해야 하는 문제입니다.

풀이 과정

from collections import deque

n = int(input())
graph = []
graphIdx = deque()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
d_left = [(-1, 0, 0.01), (1, 0, 0.01), (-1, -1, 0.07), (1, -1, 0.07), (-2, -1, 0.02), (2, -1, 0.02), (-1, -2, 0.10),
          (1, -2, 0.10), (0, -3, 0.05), (0, -2, 0)]
d_right = [(-1, 0, 0.01), (1, 0, 0.01), (-1, 1, 0.07), (1, 1, 0.07), (-2, 1, 0.02), (2, 1, 0.02), (-1, 2, 0.10),
           (1, 2, 0.10), (0, 3, 0.05), (0, 2, 0)]
d_up = [(0, -1, 0.01), (0, 1, 0.01), (-1, -1, 0.07), (-1, 1, 0.07), (-1, -2, 0.02), (-1, 2, 0.02), (-2, -1, 0.10),
        (-2, 1, 0.10), (-3, 0, 0.05), (-2, 0, 0)]
d_down = [(0, -1, 0.01), (0, 1, 0.01), (1, -1, 0.07), (1, 1, 0.07), (1, -2, 0.02), (1, 2, 0.02), (2, -1, 0.10),
          (2, 1, 0.10), (3, 0, 0.05), (2, 0, 0)]

for i in range(n):
    graph.append(list(map(int, input().split())))


def indexing():
    x, y = n // 2, n // 2
    depth = 0

    while True:
        for i in range(4):
            if i % 2 == 0:
                depth += 1
            for j in range(depth):
                graphIdx.append((x, y, i))
                if x == 0 and y == 0:
                    return
                x += dx[i]
                y += dy[i]


def tornado(x, y, d):
    global answer

    nx = x + dx[d]
    ny = y + dy[d]
    tmp = graph[nx][ny]
    graph[nx][ny] = 0

    outSand = 0
    total = 0

    if d == 0:
        dir = d_left
    elif d == 1:
        dir = d_down
    elif d == 2:
        dir = d_right
    else:
        dir = d_up

    for i in range(9):
        ddx = dir[i][0]
        ddy = dir[i][1]
        ratio = dir[i][2]

        if x + ddx < 0 or x + ddx >= n or y + ddy < 0 or y + ddy >= n:
            outSand += int(tmp * ratio)
            answer += int(tmp * ratio)
            continue
        else:
            graph[x + ddx][y + ddy] += int(tmp * ratio)
            total += int(tmp * ratio)

    if x + dir[9][0] < 0 or x + dir[9][0] >= n or y + dir[9][1] < 0 or y + dir[9][1] >= n:
        answer += (tmp - total - outSand)
    else:
        graph[x + dir[9][0]][y + dir[9][1]] += (tmp - total - outSand)


answer = 0
indexing()
while graphIdx:
    x, y, d = graphIdx.popleft()
    if x == 0 and y == 0:
        break
    tornado(x, y, d)

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/20056

문제 설명

문제의 자세한 설명은 위 링크를 참조하시길 바랍니다.

이 문제는 구현 시뮬레이션 문제로, 문제에서 요구하는 사항이 꽤 많고 상세합니다. 

빠짐없이 체크하여 어떻게 구현해야 할지 구상한 후에 구현해야 하는 문제입니다.

풀이 과정

① 먼저 초기의 파이어볼을 입력받은 후에 fireball라는 큐와 graph의 각 칸에 파이어볼을 삽입합니다.

fireball 큐는 현재 존재하는 파이어볼의 위치를 저장하는 큐이고

graph는 N x N 그래프(맵 전체)를 나타냅니다.

이 때, graph의 각 칸에는 그 칸에 존재하는 모든 파이어볼의 정보(질량, 방향, 속력)를 저장합니다.

② 파이어볼을 큐에서 꺼냅니다.

꺼낸 파이어볼의 칸으로 가서 파이어볼 정보를 꺼낸 후(pop) 이 정보를 토대로 파이어볼을 이동 시킵니다.

(이동은 옮길 칸에 정보(m, s, d)를 넣어줍니다.)

이 때, 아직 파이어볼이 합쳐질지 말지는 모르기 때문에 파이어볼큐에는 파이어볼을 넣지 않습니다.

③ 이동이 끝난 후, 파이어볼이 2개 이상 존재하는 칸은

문제에서 제시한 규칙대로 파이어볼을 하나로 합친 후에 4개로 나눕니다.

④ 나누어졌다면 바뀐 정보를 다시 해당 칸에 넣어주고, 위치는 fireball 큐에 삽입합니다.

⑤ 파이어볼이 1개만 존재하는 칸은 그대로 다시 파이어볼에 삽입합니다.

② ~ ⑤ 과정을 K번 반복한 후 정답을 출력하면 됩니다.

from collections import deque

n, m, k = map(int, input().split())
graph = [[deque() for _ in range(n)] for _ in range(n)]

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
fireball = deque()

for i in range(m):
    r, c, m, s, d = map(int, input().split())
    fireball.append([r-1, c-1])
    graph[r-1][c-1].append(deque([m, s, d]))

for _ in range(k):
    for j in range(len(fireball)):
        r, c = fireball.popleft()
        m, s, d = graph[r][c].popleft()
        nr = (r + s*dx[d]) % n
        nc = (c + s*dy[d]) % n
        graph[nr][nc].append(deque([m, s, d]))

    for i in range(n):
        for j in range(n):
            if len(graph[i][j]) > 1:
                sum_m, sum_s, odd_d, even_d, cnt = 0, 0, 0, 0, 0
                while graph[i][j]:
                    m, s, d = graph[i][j].popleft()
                    sum_m += m
                    sum_s += s
                    cnt += 1
                    if d % 2 == 0:
                        even_d += 1
                    else:
                        odd_d += 1
                sum_m //= 5
                if sum_m == 0:
                    continue
                sum_s //= cnt
                if even_d == cnt or odd_d == cnt:
                    dir = [0, 2, 4, 6]
                else:
                    dir = [1, 3, 5, 7]
                for d in range(4):
                    fireball.append([i, j])
                    graph[i][j].append(deque([sum_m, sum_s, dir[d]]))
            elif len(graph[i][j]) == 1:
                fireball.append([i, j])

answer = 0
for i in range(n):
    for j in range(n):
        answer += sum(arr[0] for arr in graph[i][j])

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/21611

문제 설명

문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.

이 문제는, 특별한 알고리즘 없이 문제에서 주어진 사항을 구현하는 문제이지만

구현해야 하는 부분들이 굉장히 까다로운 문제였습니다

풀이 과정

풀이과정이 굉장히 길기 때문에, 잘 모르시는 부분을 중점으로 보시는 것을 추천드립니다.

① 먼저, 가운데 칸(n//2, n//2)은 상어가 있는 곳이며 여기를 시작으로 하여 토네이도처럼 돌아

각 칸에 인덱스를 붙여줘야 한다.(1, 2, 3... n*n)

이 부분은 indexing함수에서 구현하였다.

② 그리고 상어가 마법을 시전하는데, 이 부분은 magic함수에 구현하였다.

위 아래 왼쪽 오른쪽 4방향중에 1방향과 거리가 주어지며

마법 후 해당 칸의 숫자는 사라진다.

해당칸을 0으로 표현함으로써 사라졌음을 표시하였다.

③ 사라진 후에는 빈 칸만큼 뒷 칸들이 당겨야 하기 때문에 이부분은 fill_blank 함수에 구현하였다.

1번 칸부터 순서대로 돌면서 0인 칸(즉, 빈칸)을 발견하면 그 칸을 blankIdx라는 큐에 넣어준 상태로

빈 칸을 만나지 않았을 때, 큐에서 빈칸의 인덱스를 꺼내어

그 칸에 현재 칸의 수를 넣어주고, 현재 칸은 0으로(빈 상태) 만들어줌으로써 당겨주었다.

모두 당겨질 때 까지 반복한다.

④ 이제, 연속된 숫자가 4칸 이상 존재한다면 그 칸들을 폭발시킨다.

이 부분은 bomb 함수에 구현하였다.

처음에는 저장할 숫자가 없으므로 임시로 -1을 지정하였고

칸을 돌면서 전 칸과 같은 숫자가 발생한다면 카운트를 늘려나간다.

그러다가 저장하고 있는 숫자와 다른 수를 만났을 때, 저장하고 있는 수의 카운트가 4 이상이라면 폭발해야하므로

그 칸들을 모두 0으로 바꿔준다. 그리고 점수계산을 해야 하므로 점수도 함께 저장한다.

⑤ 폭발 후에는 그룹을 지어야 한다.

이 부분은 grouping 함수에 구현하였다.

from collections import deque

n, m = map(int, input().split())
graph = []
cmd = []
score = [0]*3

def indexing():
    x, y = n // 2, n // 2
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    depth = 0

    while True:
        for i in range(4):
            if i % 2 == 0:
                depth += 1
            for j in range(depth):
                x += dx[i]
                y += dy[i]
                graphIdx.append((x, y))
                if x == 0 and y == 0:
                    return


def magic(dir, dist):
    x, y = n // 2, n // 2
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(dist):
        x += dx[dir]
        y += dy[dir]
        if x < 0 or x >= n or y < 0 or y >= n:
            break
        graph[x][y] = 0

    fill_blank()
    while bomb():
        fill_blank()
    grouping()


def fill_blank():
    blankIdx = deque()
    for x, y in graphIdx:
        if graph[x][y] == 0:
            blankIdx.append((x, y))
        elif graph[x][y] > 0 and blankIdx:
            nx, ny = blankIdx.popleft()
            graph[nx][ny] = graph[x][y]
            graph[x][y] = 0
            blankIdx.append((x, y))


def bomb():
    visited = deque()
    cnt = 0
    num = -1
    flag = False
    for x, y in graphIdx:
        if num == graph[x][y]:
            visited.append((x, y))
            cnt += 1
        else:
            if cnt >= 4:
                score[num-1] += cnt
                flag = True

            while visited:
                nx, ny = visited.popleft()
                if cnt >= 4:
                    graph[nx][ny] = 0

            num = graph[x][y]
            cnt = 1
            visited.append((x, y))

    return flag


def grouping():
    cnt = 1
    tmpx, tmpy = graphIdx[0]
    num = graph[tmpx][tmpy]
    nums = []

    for i in range(1, len(graphIdx)):
        x, y = graphIdx[i][0], graphIdx[i][1]
        if num == graph[x][y]:
            cnt += 1
        else:
            nums.append(cnt)
            nums.append(num)
            num = graph[x][y]
            cnt = 1

    idx = 0
    for x, y in graphIdx:
        if not nums:
            break
        graph[x][y] = nums[idx]
        idx += 1
        if idx == len(nums):
            break

for i in range(n):
    graph.append(list(map(int, input().split())))

for i in range(m):
    d, s = map(int, input().split())
    cmd.append((d, s))

graphIdx = deque()
indexing()

for a, b in cmd:
    magic(a-1, b)

answer = 0
for i in range(3):
    answer += (i+1) * score[i]

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !