코뚫하 :: 2021 동계 모각코 2회차 결과

문다연·2021년 1월 6일

코뚫하 :: 2021 동계 모각코

목록 보기

4/21

21.01.06. (수) 20시 ~ 23시

문다연
https://www.acmicpc.net/problem/2252
BOJ 2252 줄세우기 문제를 풀어보았다. 위상정렬은 2학기 과목이었던 알고리즘 과목에서도 배운 알고리즘이였고, 수업 이전에 2252 문제를 당시에는 안풀려서 고군분투했던 기억이 있었다. 그런데 위상정렬을 알고나니 바로 풀려서 여러 알고리즘 학습에 대해 필요성을 느끼게 되었다.

문혜림
『결과』

조건문, 반복문 문법 학습
중첩반복문을 사용하여 별 모양 찍기

반복문(for, while)
a = range(1, 11)
print(list(a))
for i in range(10):
print(i) # 0 1 2 ... 9
for i in range(10, 0, -1): # 1씩 작아짐
print(i) # 10 9 8 ... 1

while문

i = 1
while i <= 10:
    print(i)
    i = i+1  # 1씩 증가

i = 10
while i >= 1:
    print(i)
    i = i-1  # 1씩 감소

무한반복

i = 1
while True:
    print(i)
    if i == 10:
        break
    i += 1

continue

for i in range(1, 11):
    if i % 2 == 0:
        continue
    print(i)
    
##### for-else
for i in range(1, 11):
    print(i)
    if i==5:
        break
else:
    print(11) # break를 당해 출력 X

반복문을 이용한 문제풀이
1) 1부터 N까지 홀수 출력
2) 1부터 N까지의 합 구하기
3) N의 약수 출력

1)

n = int(input())  # input()은 str이므로 꼭 형변환!
for i in range(1, n+1):
    if i % 2 != 0:
        print(i)

2)

sum = 0
for i in range(1, n+1):
    sum += i
print(sum)

3)

for i in range(1, n+1):
    if n % i == 0:
        print(i , end=' ') # 줄 안바꿈

중첩 반복문(2중 for문)

for i in range(5):
    for j in range(i+1):
        print("*", end=' ')
    print()

for i in range(5):
    for j in range(5-i):
        print("*", end=' ')
    print()

박형기
1. 위상정렬 기본 문제를 풀어보았다.
각 노드에게 위상값을 설정해준뒤, 그 위상값이 먼저 0이 되는 노드를 탐색 및 출력을 해주면 된다.
이 문제에서는 2개 이상의 위상값이 동일하게 0일경우에 따로 정해진 순서는 없었다.
2. 위상정렬 심화문제
● 그래프를 ArrayList[배열] 로 만든 이유
작년 순위에서 순위를 변경하기 위해선 그래프 방향을 변환해 주어야 했다.
예를 들면 5 4 3 2 1이 작년 순위 일 경우, 4 에서 2 방향으로 연결이 된 간선이 있을것이다.
이때 2 와 4 사이의 간선 방향을 변경하기 위해 ArrayList의 4번째 안에서, 2를 찾아 없애 주어야했다.
하지만 ArrayList안에 배열로 만들어 주고, 배열[2]에 2를 저장하게 되면, 배열[2] = 0 을 해주면 된다.
이후에 위상정렬 하면서 배열을 다 탐색해야한다는 점에서 시간복잡도는 손해일수도 있었지만, 코딩 자체는 좀더 편리했다.
처음에 위상 기준을 정하는것과 그래프 간선 연결을 하며 일관성이 없다는것을 어떤식으로 판별할지 고민했으나
작년 순위를 바탕으로 전부다 연결해주고, 변경된 순위의 간선만 변경 해주었더니 생각보다 간단했다.

유정균
백준 3273 두 수의 합 (투포인터)

이 문제는 여러 수들과 목표인 수를 입력받고 그 수들중 한쌍의합이 목표가 되게하고 그 개수가 얼마나있는지 묻는 문제이다
이문제는 두개의 int형 변수(p1, p2 배열의 인덱스를 나타내줄것)를 포인터처럼 사용해서 풀었다
먼저 입력받은 여려수를 개수만큼 배열에 저장해준다
이때 정리가되있지않으므로 Sort를 사용해 오름차순으로 정렬해준다
그런다음 p1 = 0, p2 = 배열의 마지막 으로저장해서 두 위치의 합을 계산해준다
그런다음 목표와같다면 p1은 1씩 더하고 p2는 1씩 빼준다 그러면서 개수를 1개센다
(이문제에서는 모두 다른 수이므로 이렇게 해줘도 상관없다)
그러나 합이 목표보다 크다면p2 만 1빼주고 작다면 p1만 1더해주면된다
이 방법을 p1이 p2 보다 커질때까지 반복해주면된다