안녕하세요? 선생님들, 3월에 ‘파이썬으로 개미 수열 구하기’ 기억나시나요? ㅎㅎ
새 학기의 시작인 3월에 개미로 시작했으니.. 끝도 개미로 준비했습니다 
이번 1월 PS 주제는 ‘애드 혹’입니다.
애드 혹?? 아마 처음 들어보신 분이 많으실 것이라고 생각이 되는데요!
위키 백과에서는 ‘애드 혹’을 이렇게 정의하고 있습니다.
정리하자면! 보통 문제를 풀 때 어떤 정형화된 알고리즘을 적용해서 푸는 경우가 많은데, 아이디어만 있어도 문제를 해결할 수 있는 유형을 애드 혹이라고 합니다.문제
개미 N마리가 나무 판자 위에서 행진을 하고 있다. 개미는 1초에 1cm씩 앞으로 전진한다. 두 개미가 같은 곳에서 만나게 되면, 즉시 방향을 바꾸고 반대 방향으로 전진하게 된다. 개미가 나무의 끝에 도착하게 되면, 개미는 땅으로 떨어지고, 다른 개미에게 영향을 끼칠 수 없게 된다. (개미의 크기는 무시할 수 있다)
위의 그림은 시간이 0인 순간이다. 1초가 지난 후에 E와 A는 2에서 만나고, 두 개미는 방향을 바꾸게 된다. 1.5초가 지난 후에는 A와 B가 만나게 되고 동시에 C와 D도 만나게 된다. 네 마리의 개미는 모두 방향을 바꾼다. 0.5초가 지난 후 (3초)에는 E가 땅으로 떨어지게 된다.
개미의 움직임을 시뮬레이트하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 나무의 길이 L (단위: cm, 1 ≤ L ≤ 99,999)과 개미의 수 A (1 ≤ A ≤ L+1)가 주어진다.
다음 A개 줄에는 개미의 위치 Xi (0 ≤ Xi ≤ L)와 개미가 바라보고 있는 방향 (L: 왼쪽, R: 오른쪽)이 주어진다. 두 개미가 같은 위치에 있는 경우는 없다.
입력 예시
90000 1
0 R
10 1
0 L
14 5
3 L
6 L
13 L
8 R
1 R
Plain Text
복사
출력
각 테스트 케이스 마다, "The last ant will fall down in T seconds - started at P."를 출력한다.
T는 마지막 개미가 떨어진 시간, P는 그 개미가 시간 0 때 있었던 위치이다. 두 개미가 동시에 떨어지는 경우에는 "started at P and Q"를 출력한다. (P < Q)
출력 예시
The last ant will fall down in 90000 seconds - started at 0.
The last ant will fall down in 0 seconds - started at 0.
The last ant will fall down in 13 seconds - started at 6 and 8.
Plain Text
복사
초코쌤의 문제 풀이
입력 예시
90000 1
0 R
위와 같이 입력한 경우를 그림으로 표현해보면 초기와 시작부터 1초 후가 이렇게 그려지고,
1초마다 개미가 열심히 가다가.. 90000초 후에 떨어지며,
The last ant will fall down in 90000 seconds - started at 0.가 출력됩니다.
입력 예시
14 5
3 L
6 L
13 L
8 R
1 R
위와 같이 입력한 경우를 그림으로 표현해보면 초기와 시작부터 1초 후와 2.5초가 이렇게 그려지고, 개미가 만나고 방향이 바뀌면서.. 13초 뒤에 동시에 떨어지며,
will fall down in 13 seconds - started at 6 and 8.가 출력됩니다.
출처: 국가교육과정정보센터 > 2022 개정 시기 > 고등학교 교육과정
아래는 2022 개정 교육과정에서 도입되는 객체, 클래스와 관련된 성취기준입니다.
[12정03-08] 객체를 구현하는 클래스와 인스턴스를 활용하여 프로그램을 작성한다.
저는 클래스와 정렬을 활용한 문제 풀이를 해보도록 하겠습니다.
초코쌤의 Python 풀이
먼저, 아래 코드를 이해하기 위해 간단한 문법 설명을 하도록 하겠습니다.
위 성취 기준에서 제시된 클래스와 인스턴스에 대한 용어를 알아보겠습니다.간단하게 정의하자면, 클래스 = 틀, 인스턴스 = 실체(객체)라고 생각하면 됩니다.
흔한 예를 들어보면
클래스 = 붕어빵 틀, 인스턴스 = 붕어빵
붕어빵 틀에 어떤 재료를 넣느냐에 따라 팥 붕어빵, 슈크림 붕어빵.. 등 다양한 붕어빵을 만들 수 있습니다.
쉽게 생각한다면, 서로 다른 자료형을 묶을 수 있는 ‘C언어의 구조체’라고 생각하시면 됩니다! ___init___ 메서드(함수)init이 무엇인가요? 초기화라는 뜻입니다.
def __init__():
Python
복사
def는 함수를 정의할 때 쓰죠? 그래서 이 문법은 초기화 함수로, 어떤 클래스의 객체가 만들어질 때 자동으로 호출되는 함수입니다.
class Ant:
def __init__(self, pos, direction):
self.m_pos = pos
self.m_direction = direction
Python
복사
먼저, 개미라는 클래스를 만들겠습니다.
문제에서 개미는 위치와 방향을 가지고 있습니다. 따라서 실제 개미의 머리, 다리 등 디테일한 정보는 불필요하므로 제외합니다.
예외 처리(try, except)입력이 더 이상 없을 때까지 받기 위해서 ‘except EOFError(End of File)’를 활용합니다.
while True:
try:
TreeLength, Antcnt = map(int, input().split())
except EOFError:
break
Python
복사
초코쌤의 Python 전체 코드
# Ant 클래스
# 멤버변수 m_pos, m_direction.
# 메서드 __init__는 이러한 속성을 기본값으로 초기화합니다.
# 이 클래스는 특정 위치와 방향을 가진 개미를 표현
class Ant:
def __init__(self, pos, direction):
self.m_pos = pos
self.m_direction = direction
# 나무의 길이와 개미의 수를 입력으로 받음
while True:
try:
TreeLength, Antcnt = map(int, input().split())
except EOFError:
break
# 각 개미의 이동에 따라 떨어지는 시간을 계산할 값
seconds = -1
ants = [] # 개미들을 보관할 리스트
for _ in range(Antcnt):
pos, direction = map(str, input().split())
pos = int(pos)
ants.append(Ant(pos, direction))
# 개미의 방향에 따라 가장 먼 거리(TreeLength)에 있는 개미를 찾고
# 그 거리를 seconds 변수에 저장함.
if direction == 'L':
# 왼쪽: 가장 왼쪽 끝(0)에서 가장 멀리 있는 개미의 위치를 저장
seconds = max(seconds, pos)
else:
# 오른쪽: 오른쪽 끝(TreeLength)에서 가장 멀리 있는 개미의 위치를 저장
seconds = max(seconds, TreeLength - pos)
print("The last ant will fall down in",seconds, "seconds - started at ", end='')
# 개미가 시간 0 때 있었던 위치
# 개미들을 보관할 리스트를 pos를 기준으로 정렬하고
ants.sort(key=lambda ant: ant.m_pos)
# 각 개미의 이동거리를 계산 리스트
ant_moved = [] #개미가 이동했을 때에 대한 보관 리스트
# 처음에 개미들을 보관한 리스트에서 개미들을 꺼내서
# ant_moved 리스트에 각 개미가 이동한 위치를 저장함.
# seconds를 사용하여 가장 먼 거리에 있는 개미의 위치를 기준으로 이동한 위치를 계산
# 이렇게 계산된 ant_moved 리스트를 정렬하여 마지막 떨어지는 개미의 위치를 찾음.
for ant in ants:
if ant.m_direction == 'L':
ant_moved.append(ant.m_pos - seconds)
else:
ant_moved.append(ant.m_pos + seconds)
# 움직인 거에 대한 개미 리스트 정렬 문제에서 P<Q기 때문에
ant_moved.sort()
# 마지막 개미가 없다고 치는데
no_last_ants = 0
# 움직인 개미 중에서
# moved == 0(개미가 왼쪽 끝에 도달하여 땅으로 떨어짐)움직임이 없었거나, 오른쪽 끝에 가 있다면
# moved == TreeLength (개미가 오른쪽 끝에 도달하여 땅으로 떨어짐)
# 하나를 출력하고, 개미가 있으니까 ants를 하나 증가시켜서
# and 출력 후에 그 다음 개미에 따라 나머지도 출력한다.
# 각각의 개미는 1초에 1cm씩 움직임.
# 두 개미가 같은곳에서 만나게 되면(충돌하게 되면) 반대 방향으로 전진한다는 것은
# 그 순간에 떨어지는거랑 같음.
#enumerate: 리스트의 요소와 인덱스를 한번에, i: 인덱스, moved: 값
for i, moved in enumerate(ant_moved):
if moved == 0 or moved == TreeLength:
if no_last_ants == 1:
print(" and ", end='')
print(ants[i].m_pos, end='')
no_last_ants += 1
print(".")
Python
복사
위 코드를 차례대로 따라가면 흐름은 다음과 같습니다.
선생님들의 다양한 아이디어를 활용한 문제 풀이를 기대합니다
koistudy.net 개미 이동 문제 변형_C언어 코드
와~ 초코쌤이 이해하기 쉽게 설명해 주셨네요.
저는 코이스터디의 변형된 문제로 풀어보도록 하겠습니다.
문제를 같이 살펴볼까요?
길이가 L(cm)인 막대 위에 N마리의 개미가 초당 1cm의 속도로 걸어가고 있다.
개미는 장대의 끝에 도착하면 장대 아래로 떨어진다.
또한 장대 위는 좁아서 개미가 서로 지나갈 수 없이 반대 방향으로 돌아가야만 한다.
문제는 장대 위에 N마리의 개미의 위치가 주어진다. 모든 개미가 장대 위에서 떨어지는 최대 시간과 최소 시간을 구하는 프로그램을 작성하시오. (개미의 초기 이동 방향에 따라 모든 개미가 떨어지는 시간은 달라진다.)
모든 개미는 반드시 1초에 1cm씩 이동한다.
두 개미가 충돌하는 순간 바로 반대 방향으로 이동하기 시작하며 방향 전환 시간은 0이다.
모든 개미의 출발 시 이동 방향은 알 수 없다.
Input
첫 번째 줄에 장대의 길이 L과 개미의 수 N 이 공백으로 구분되어 입력된다.
두 번째 줄에 각 개미의 초기 위치의 좌표가 주어진다.
•
L의 범위는 3 ~ 100000000인 자연수이다. ( 만약 막대의 길이가 5라면 0 ~ 5까지의 좌표를 가진다. )
•
N의 최대값은 10000을 넘지 않는 자연수이다.
Output
모든 개미가 떨어지는 최소 시간과 최대 시간이 공백으로 구분되어 출력된다.
IO Example
입력
10 3 → 10 cm 길이의 장대에 3마리의 개미가 있다.
2 6 7 → 좌표 2, 6, 7 이 개미의 초기 위치이다. 이 때 각 개미의 방향은 랜덤하다.
출력
4 8
→ 최소시간은 4초 후에 모든 개미가 떨어진다.
→ 최대 시간은 8초 후에 모든 개미가 떨어진다.
#include <stdio.h>
int i;
double n, a, b, l, min, max;
int main() {
scanf("%lf %lf", &l, &n); // l : 장대의 길이 , n : 개미 수
min = l/2; max = 0; // 장대 길이의 1/2를 넘는지
for (i = 0; i < n; i++) // 개미 수 만큼 반복한다.
{
scanf("%lf", &a); // 개미의 좌표를 입력받는다.
b = l/2-a>0? l/2-a:a-l/2; // 새로 입력 받은 좌표가 장대의 1/2 보다 작으면 그대로
// 아니면 장대의 1/2을 뺀 값을 b에 넣는다
if(min>b) min = b; // b를 min과 비교하여 min 값을 갱신한다.
if(max < b) max = b; // b를 max와 비교하여 max 값을 갱신한다.
}
printf("%d %d",(int)(l/2-min), (int)(max+l/2));
// 최소값은 장대의 1/2에서 min을 뺀 값이다.
// 최대값은 장대의 1/2에서 max를 더한 값이다.
}
C
복사