알면 도움되는 코딩 테스트 유형: 2) #Ad_Hoc

• 이번에는 애드 혹(Ad Hoc) 유형의 문제를 해결하는 방법과 코딩 테스트에서 이러한 문제에 접근하는 방법에 대해 설명하겠습니다.

 

애드 혹(Ad Hoc)이란?

• 애드 혹은 "특정 상황에 맞춰서"라는 뜻을 가지고 있습니다. 알고리즘 분류 중에서도 일종의 잡다한 문제 유형으로 분류됩니다. 이러한 문제들은 주로 직관과 간단한 로직을 활용하여 해결할 수 있으며, 복잡한 자료구조나 알고리즘이 필요하지 않은 경우가 많습니다.

 

애드 혹 문제 해결 전략

• 애드 혹 유형의 문제는 주로 실생활에서 우리가 자주 마주치는 상황과 유사하거나 실제 데이터에 적용할 수 있는 경우가 많습니다. 따라서 일상적인 경험과 직관을 활용하여 문제에 접근하면 도움이 됩니다.
• 코딩 테스트에서 애드 혹 유형의 문제를 효율적으로 해결하기 위해서는 다음과 같은 팁을 고려할 수 있습니다.

 

1. 예시와 패턴 파악: 주어진 예시와 패턴을 분석하여 규칙성이나 특정한 동작 방식을 파악합니다. 이러한 규칙성이나 패턴은 문제 해결에 큰 도움이 됩니다.
2. 데이터 구조 활용: 애드 혹 유형의 문제에서는 복잡한 자료구조보다는 기본적인 데이터 구조(배열, 리스트, 문자열 등)를 활용하는 경우가 많습니다. 이러한 데이터 구조를 잘 다룰 수 있어야 합니다.
3. 문자열 처리: 문자열 처리는 애드 혹 유형의 문제에서 자주 사용되며, 문자열 연산 및 조작 기법에 익숙해져야 합니다. 문자열 분리, 결합, 검색 등의 작업을 숙달해야 합니다.
4. 수학적 사고력: 애드 혹 유형의 문제에서 수학적인 사고력은 매우 중요합니다. 수식 계산, 최대/최소값 찾기, 정수론 등 다양한 수학 개념과 연산을 활용할 수 있어야 합니다.
5. 시뮬레이션: 시뮬레이션은 애플리케이션 개발과 비슷하게 동작하는 과정입니다. 주어진 조건에 따라 상태 변화를 시뮬레이션하여 원하는 결과를 얻는 방식으로 접근할 수 있습니다.
6. 문제 분해와 하위 문제 해결: 복잡한 애플리케이션처럼 애드 혹 유형의 문제를 해결하기 위해 문제를 분해하여 하위 문제로 나누고, 각각의 하위 문제를 해결하는 방식으로 전체적인 문제를 해결할 수 있습니다. 큰 문제를 작은 단위로 쪼개어 해결하면서 점진적으로 전체적인 결과를 얻을 수 있습니다.

 

10158번: 개미

  문제  

• 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

• 위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다. 
• 여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. 
• 문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다.

 
  해결 방법  

• 먼저 개미가 움직일 수 있는 패턴을 찾아보겠습니다. 개미는 상자의 경계에 도달하면 반대 방향으로 움직입니다. 이러한 움직임은 사실상 두 축(x축과 y축)에서 독립적으로 일어나므로, 각 축에서 개미가 어디에 위치할지 따로 계산할 수 있습니다.

def ant_position(w, h, p, q, t):
    x = (p + t) % (w * 2)
    y = (q + t) % (h * 2)
    if x > w:
        x = w * 2 - x
    if y > h:
        y = h * 2 - y
    return x, y

w, h = map(int,input().split())
p, q = map(int,input().split())
t = int(input())
print(*ant_position(w, h, p, q, t))

• 위 코드에서 ant_position 함수는 주어진 시간 t 후에 개미의 위치를 반환합니다. (p+t)와 (q+t) 값들을 각각 w*2와 h*2로 나누어주면 경계를 넘어선 경우 반대쪽 끝에서 다시 시작하는 것과 같은 효과를 줍니다. 그러나 이렇게 계산된 좌표가 실제 벽에 부딪친 후의 좌표일 수도 있으므로 확인해서 필요한 경우 수정해줍니다.

 

1034번: 램프

  문제  

• 지민이는 각 칸마다 (1×1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. 켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)
• 만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.
• 지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

 
  해결 방법  

• 램프 문제는 간단하게 보면 스위치를 켜고 끄는 것이지만, 사실은 그 이상입니다. 여기서 중요한 것은 '가능한 많은 행을 켜는 것'이라는 목표를 달성하기 위해 어떤 행을 선택하고, 그 행의 스위치를 몇 번 눌러야 하는지를 결정하는 것입니다. 이 문제에서 Ad-Hoc 접근법은 다음과 같습니다.

1. 각각의 행에 대해 해당 행을 켤 수 있는 최대 횟수를 계산합니다.
2. 최대값을 가진 모든 행에 대해 그들이 켜질 수 있는지 확인합니다.

 

• 여기서 '켜질 수 있다'는 의미는, 해당 스위치를 K번 누르면 모든 램프가 켜진다는 것입니다. 이것은 모든 '0'이 짝수 개 있어야 하며, K번 누른 후에도 남아있다면 그것은 홀수 번 반복되어야 합니다.

import sys; input=sys.stdin.readline

N, M = map(int,input().split())
lamp = [list(map(int, list(input().rstrip()))) for _ in range(N)]
K = int(input())

def check_possible(lamp_line, K):
    zero_cnt = lamp_line.count(0)
    if zero_cnt > K: return False
    elif zero_cnt % 2 != K % 2: return False
    else: return True

max_light = 0
for i in range(N):
    if check_possible(lamp[i], K):
        light = lamp.count(lamp[i])
        max_light = max(max_light, light)

print(max_light)

• Ad-Hoc 방식은 알고리즘이나 패턴에 의존하지 않고, 문제의 특성과 요구사항을 깊이 이해하고 그에 따라 해결책을 찾아내는 방식입니다. 이런 접근법은 코딩 테스트에서 매우 중요하며, 실제로 많은 문제들이 이런 방식으로 해결됩니다.
• 그러나 Ad-Hoc 접근법은 문제의 특성을 정확히 파악하는 것이 중요하기 때문에, 이해하지 못하면 문제를 해결하는 데 어려움을 겪을 수 있습니다. 따라서, 여러 유형의 Ad-Hoc 문제를 많이 풀어보고 다양한 상황에 대응할 수 있는 능력을 기르는 것이 중요합니다.