이번주 월요일과 화요일은 코딩테스트 & 알고리즘 수업 특강이 있었다.
외부에서 코딩테스트와 다른 과목들을 전문적으로 수업해주시는 강사분이셨는데 이번에 프로젝트 전 최종으로 코딩 관련 내용을 복습하며 알고리즘 수업을 진행해주시러 오셨다.
그 중 기억에 남는 개념, 문제 등을 정리해보려 한다.
코딩테스트시 입력 받는법
a, b = map(int, input().split())
if a % b == 0 and a + b <= 100:
print("YES")
else:
print("NO")
print("프로그램 종료")
지금까지 프로그래머스와는 다르게 입력값을 입력받는 법에 있어서 새로운 방법을 사용했다.
사용자가 입력받는 함수인 input()를 사용하고, 그 값을 공백으로 split()으로 나눠준다, 그 값을 int로 받으며 map함수로 이것들을 모든 변수에 적용해주고 값을 a,b로 받아준다.
그 이후에 그 값들을 코딩을 하며 답을 출력하는것이 코딩테스트의 기본이었다. 이건 완전히 몰랐다
array
type을 입력 받고, type에 따른 결과를 출력하는 프로그램을 작성하세요.
[type 1]
N개의 정수들을 입력 받고, 입력된 정수들을 반대로 출력합니다.
[type 2]
N개의 정수들을 입력 받고, a와 b 위치를 입력 받습니다.
a와 b 두 위치의 정수들을 교체한 후, 배열의 정수들을 순서대로 출력합니다.
입력
첫번째 줄에 type을 입력 받습니다. (1 <= type <= 2)
두번째 줄에 정수의 개수 N을 입력 받습니다. (1 <= N <= 100)
세번째 줄에 N개의 정수들을 입력 받습니다. (0 <= 정수 <= 1,000,000)
type 이 2라면, 네번째 줄에 위치 a와 b를 공백으로 구분하여 입력 받습니다. (1 <= a, b <= N)
출력
주어진 type에 맞는 결과를 출력합니다.
type2의 경우 index는 사람이 보는 순서와 다를 수 있다는 것에 주의해 주세요.
(사람의 첫(1)번째 = 컴퓨터의 0번쨰)
입력 예시 1
1
5
1 2 3 4 5출력 예시 1
5 4 3 2 1입력 예시 2
2
5
1 2 3 4 5
5 2출력 예시 2
1 5 3 4 2
ty = int(input())
if ty == 1:
n = int(input())
arr = list(map(int, input().split()))
for i in range(n-1 ,-1, -1):
print(arr[i], end = ' ')
elif ty == 2:
n = int(input())
arr = list(map(int, input().split()))
a, b = map(int, input().split())
temp = arr[a-1]
arr[a-1] = arr[b-1]
arr[b-1] = temp
for i in range(n):
print(arr[i], end = ' ')배열의 포인트는 type = 2 일때다.
arr[n]의 값을 temp에 넣어두고, 그를 넣어야 올바르게 인덱스의 값들이 바뀌는것이다.
nested loop
N을 입력 받고, 아래와 같이 숫자 삼각형을 출력하는 프로그램을 작성해 주세요.
[예시]
- N = 5
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5입력
첫번째 줄에 양의 정수 N이 입력됩니다. (1 <= N <= 10)
출력
숫자 삼각형을 출력합니다.
입력 예시 1
5출력 예시 1
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5입력 예시 2
3출력 예시 2
1
1 2
1 2 3
N = int(input())
for i in range(2, N + 2, 1):
for j in range(1, i, 1):
print(j, end = " ")
print()
이는 이중반복문의 기초적인 문제이다.
2~6까지의 값이 i에 들어가서 출력되어서
1
12
123
....
등등으로 나오는것이다.
그리고 j가 print되니까 저 내용들이 print 되는것이다.
2d array
N x N 크기의 2차원 배열을 입력 받고, 열의 합이 가장 큰 열 번호와 합을 출력하는 프로그램을 작성하세요.
입력
첫번째 줄에 N이 입력됩니다. (1 <= N <= 10)
두번째 줄부터 N개의 줄에 걸쳐 N개의 정수가 공백으로 구분되어 주어집니다.
출력
열의 합이 가장 큰 열의 번호를 출력하고, 공백을 둔 후 해당 열의 합을 출력합니다.
입력 예시 1
3
1 3 9
1 3 9
1 3 90출력 예시 1
2 108입력 예시 2
5
1 2 3 4 5
5 4 3 2 1
-1 -1 -1 -2 -1
4 5 6 7 8
9 8 7 6 5출력 예시 2
0 18
N = int(input())
arr = []
for i in range(N):
temp = list(map( int, input().split()))
arr.append(temp)
# print(arr)
sum_row = 0 # 가장 큰 행의 합
row = 0 # 그때의 행 번호 저장
for j in range(N):
temp = 0
for i in range(N):
temp += arr[i][j]
if temp > sum_row:
sum_row = temp
row = j
print(row,sum_row)여기서 arr[ j ][ i ]로 바꿔주면 답이 나온다.
2차원 배열에 관련된 문제로 첫번째 인덱스, 두번째 인덱스의 의미를 잘 파악하면 풀 수 있는 문제이다.
인접행렬 만들기
간선정보 입력이 들어옵니다.
첫 번째줄에 노드의 갯수 N ,간선의 갯수 T가 입력 됩니다. (노드의 번호는 1 ~ N 까지 있습니다.)
다음줄 부터 T개의 간선정보가 입력됩니다.
간선정보는
A B 형태로 들어옵니다.
A,B 는 A 노드에서 B 노드로 단방향 연결을 의미합니다.
인접행렬형태로 저장하여 , 인접행렬 형태로 출력해주세요
입력
6 5 // N = 6, T = 5
1 2
1 4
2 3
4 5
4 61 <= N <= 10
1 <= T <= 100
입니다.
출력
0 번 노드는 제외하고 인접행렬을 출력해주세요
N x N 형태로 출력해주세요
입력 예시 1
6 5
1 2
1 4
2 3
4 5
4 6출력 예시 1
0 1 0 1 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 0 0
0 0 0 0 0 0
N, E = map(int, input().split())
# 인접행렬 만들기
matrix = [[0] * (N+1) for i in range(N+1)]
for i in range(E):
f, t = map(int, input().split())
matrix[f][t] = 1
for i in range(1, N+1):
for j in range(1, N+1):
print(matrix[i][j], end = " ")
print()
인접행렬이란?
특정 노드와 붙어있는 다른 노드는 무엇인지, 연결되어있는 간선은 어떤지를 확인할 수 있는 행렬이다. 위 4x4 배열을 그래프화 하면 이미지처럼 나오는것이다.
이는 어떤 값이 특정 값과 붙어있는지를 확인하기 위해 나온 내용으로 추후 알고리즘에도 사용되는 개념이다.
인접 리스트
간선정보 입력이 들어옵니다.
첫 번째줄에 노드의 갯수 N ,간선의 갯수 T가 입력 됩니다. (노드의 번호는 1 ~ N 까지 있습니다.)
다음줄 부터 T개의 간선정보가 입력됩니다.
간선정보는 A B 형태로 들어옵니다.
A,B 는 A 노드에서 B 노드로 단방향 연결을 의미합니다.
입력 순서를 따라 간선 정보를 인접 리스트 형태로 저장하여, 각 노드의 상태를 출력해 주세요.
입력
6 5 // N = 6, T = 5
1 2
1 4
2 3
4 5
4 6
1 <= N <= 10
1 <= T <= 100
입니다.
출력
0 번 노드는 제외하고 인접 리스트를 출력해주세요.
입력 예시 1
6 5
1 2
1 4
2 3
4 5
4 6출력 예시 1
1 : 2 4
2 : 3
4 : 5 6
비슷한 형태지만 행렬이 아닌, 리스트 형식으로 나오고 출력 예시에서도 전처리 과정이 들어가야 하는 난이도 높은 문제이다.
# 강사님 답
N, E = map(int, input().split())
# 인접 리스트 만들기
al = [[] for i in range(N+1)]
# 인접 리스트 데이터 채우기
for i in range(0, E):
f, t = map(int, input().split())
al[f].append(t)
# al[t].append(f)
for i in range(N):
if len(al[i]) == 0:
continue
print(f"{i} :", end = " ")
for v in al[i]:
print(v, end = " ")
print()
bfs
bfs란?
a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
큐에 방문된 노드를 삽입(enqueue)한다.
초기 상태의 큐에는 시작 노드만이 저장
즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
큐에서 꺼낸 노드를 방문한다.
큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
큐에 방문된 노드를 삽입(enqueue)한다.
큐가 소진될 때까지 계속한다.
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
그래서 우리는 함수를 정의하고 0~4까지를 입력하면 그 노드와 붙어있는 노드를 출력하는 bfs 알고리즘을 구현할것이다.
# 인접 행렬 (bfs)
from collections import deque
# 노드 엣지 입력 받기
N, E = map(int,input().split())
# 인접 행렬 만들기
matrix = [[0] * N for i in range(N)] # 0 부터 시작
# matrix = [[0] * (N + 1) for i in range(N + 1)]
for i in range(E):
f, t = map(int,input().split())
matrix[f][t] = 1 # 단방향
# matrix[t][f] = 1 # 양방향
def bfs(start):
# 준비 단계
# 1. 큐 만들기
q = deque()
# 2. 출발지를 큐에 넣기
q.append(start)
# 동작 단계
# 1. q가 빌때까지
while q:
# 2. 큐 맨 앞 뽑기
now = q.popleft() # 0
print(now , end = " ")
# 3. now와 연결되어 있는 노드를 확인
for next in range(N):
if matrix[now][next] == 0: # 연결 관계가 없다
continue
# 4. q에 넣기
q.append(next)
bfs(0)이렇게 수행하면 예를들어 1 을 입력하면 3,4를 반환하는 함수를 만들 수 있다.
네트워크 바이러스
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파됩니다.
네트워크는 양방향 연결로서, 서로 연결된 컴퓨터들들 데이터를 서로 주고 받을 수 있습니다.
한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 됩니다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 할 때
1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 됩니다.
하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않습니다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸습니다.
컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,
1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성해 주세요.
입력
첫째 줄에는 컴퓨터의 수가 주어집니다.
컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨집니다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어집니다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어집니다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력합니다.
입력 예시 1
7
6
1 2
2 3
1 5
5 2
5 6
4 7출력 예시 1
4
# 탈출코드 추가
# 인접행렬을 이용해서 bfs 구현
from collections import deque
# 노드 엣지 입력 받기
N = int(input())
E = int(input())
# 인접 행렬 만들기
# matrix = [[0] * N for i in range(N)] # 0 부터 시작이라서 이게 맞음
matrix = [[0] * (N + 1) for i in range(N + 1)] # list index out of range 무서우면 이걸로 해도 됨
for i in range(E):
f, t = map(int, input().split())
matrix[f][t] = 1 # 단방향
matrix[t][f] = 1 # 양방향
# print(matrix, end = " ")
def bfs(start):
a = -1
# 준비 단계
# 1. 큐 만들기
q = deque()
# 2. 출발지를 큐에 넣기
q.append(start)
# 3. visited 만들기
visited = [0] * (N + 1)
# 4. 출발지를 방문표시 하기
visited[start] = 1
# 동작 단계
# 1. q가 빌때까지
while q:
# 2. q 맨 앞 뽑기
now = q.popleft()
# print(now, end = ' ')
a += 1
# 3. now와 연결되어있는 노드를 확인
for next in range(1, N+1):
if matrix[now][next] == 0: # 0을 만났다? 연결관계가 없다
continue
if visited[next] == 1: # 여기 이미 방문했어
continue
# 4. 대기열 q에 다시 넣기
q.append(next)
# 5. 너 방문했어
visited[next] = 1
print(a)
bfs(1)
이렇게 bfs를 직접 구현해보는 코드까지 작성하였다. 여기서 설명 안한 부분이 있는데
visited라는 값을 추가해서 기존에 다녀온 곳이면 +1을 해서 한번 방문한 곳에는 다시 가지 않게 설정해주는 콛도 있다.
세상은 넒고 고수는 아주 많다 라는것을 느낄 수 있는 시간이었다.
오늘의 수업은 여기까지