월말평가
파리퇴치3
T = int(input())
for tc in range(1, T+1):
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
di = [-1, 1, 1, -1]
dj = [1, 1, -1, -1]
answer = []
for i in range(N):
for j in range(N):
total = arr[i][j]
for k in range(4):
for l in range(1, M):
ni = i + dx[k] * l
nj = j + dy[k] * l
if 0 <= ni < N and 0 <= nj < N:
total += arr[ni][nj]
answer.append(total)
for i in range(N):
for j in range(N):
total = arr[i][j]
for k in range(4):
for l in range(1, M):
nx = i + di[k] * l
ny = j + dj[k] * l
if 0 <= nx < N and 0 <= ny < N:
total += arr[nx][ny]
answer.append(total)
print(f'#{tc}', (max(answer)))
일차원 오델로
T = int(input())
for tc in range(1, T+1):
N, M = map(int, input().split()) #돌의 개수 N, 뒤집기 작업 횟수 M
othello = list(map(int, input().split())) #돌의 상태 (흰색 0, 검은색 1)
for _ in range(M):
pos, dol, num = map(int, input().split()) #기준 위치 pos, 작업할 돌의 개수 dol, 수행할 작업번호 num
if num == 1: #1번 작업을 수행
for i in range(pos-1, pos-1+dol):
if 0 <= i < N:
if othello[i] == 1:
othello[i] = 0
else:
othello[i] = 1
elif num == 2: #2번 작업을 수행
for i in range(pos-1, pos-1+dol):
if 0 <= i < N:
if othello[pos-1] == 1:
othello[i] = 1
else:
othello[i] = 0
else: #3번 작업을 수행
for i in range(1, dol+1):
if 0 <= pos - 1 - i and pos - 1 + i < N:
if othello[pos-1-i] == othello[pos-1+i]:
if othello[pos-1-i] == 1:
othello[pos-1-i] = othello[pos-1+i] = 0
else:
othello[pos-1-i] = othello[pos-1+i] = 1
else:
continue
print(f'#{tc}', *othello)트리 관련 서술형
이진트리란?
: 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리, 각 노드가 자식 노드를 최대한 2개까지만(왼쪽 자식 노드, 오른쪽 자식 노드) 가질 수 있는 트리, 레벨 i에서의 노드 최대 개수는 2^i개, 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^h+1 -1)개가 된다.
(참고)
포화이진트리 : 모든 레벨에 노드가 포화상태로 차있는 이진트리
완전이진트리 : 노드 수가 n개일 때, 포화 이진트리의 노드번호 1부터 n번까지 빈자리가 없는 이진트리
편향이진트리 : 높이 h에 대한 최소개수의 노드(1개)를 가지면서 한쪽방향의 자식노드만을 가진 이진트리
중위순회란?
: 순회란 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 말하는데, 트리는 비선형 구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다. 순회는 트리의 노드들을 체계적으로 방문하는 것으로, 중위 순회는 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문한다.
수행 방법>
1) 현재 노드 n의 왼쪽 서브트리로 이동한다.
2) 현재 노드 n을 방문하여 처리한다.
3) 현재 노드 n의 오른쪽 서브트리로 이동한다.
이진트리 예시 주어지면 전위/중위/후위 결과: 전위(VLR) 중위(LVR) 후위(LRV)
@@@@@@@@@@@@
트리의 개념은
-비선형구조
-일 대 다 구조를 가지는 자료구조
-원소들 간에 계층관계를 가지는 자료구조
-상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)구조
이진트리는 각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리입니다.(0개 혹은 1개 역시 가능)
레벨 i 에서 노드의 최대 개수는 2의 i제곱
높이 h인 트리에서 전체 노드의 최소개수는 h + 1(편향이진트리)최대 개수는 2의 h+1제곱 -1(포화이진트리)
순회란 트리의 각 노드들이 중복되지 않게 전부 방문하는 것, 비선형구조이기 때문에 선형구조와 다르게선후 연결관계를 알수 없어서 특별한 방법을 사용한다
전위 부모 왼쪽 오른쪽
중위 왼쪽 부모 오른쪽
후위 왼쪽 오른쪽 부모
중위를 기준으로 설명하면 현재노드에서 왼쪽 서브트리 방문-현재노드 방문하여 처리-현재노드에서 오른쪽 서브트리 방문
과목평가
풍선팡3
T = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for tc in range(1, T+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
sum_lst = []
for i in range(N):
for j in range(N):
sum = arr[i][j]
for dir in range(4):
for l in range(1, arr[i][j]+1):
nx = i + dx[dir] * l
ny = j + dy[dir] * l
if nx < 0 or ny < 0 or nx >= N or ny >= N:
continue
else:
sum += arr[nx][ny]
sum_lst.append(sum)
print(f'#{tc}', max(sum_lst) - min(sum_lst))반복문자지우기 관련 서술형
T = int(input())
for tc in range(1, T+1):
s = list(input())
stack = []
stack.append(s[0])
for i in range(1, len(s)):
if stack:
if stack[-1] == s[i]:
stack.pop()
else:
stack.append(s[i])
else:
stack.append(s[i])
print(f'#{tc}', len(stack))t = int(input())
for tc in range(1,t+1):
string = input()
stack = []
for s in string:
# 스택의 top 요소가 삽입하려는 요소와 동일하면 pop(삭제)
if stack and stack[-1] == s:
stack.pop()
# 동일하지 않으면 push
else:
stack.append(s)
print(f'#{tc} {len(stack)}')어떤 자료구조?: 스택. 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있도록 제한된 선형으로 나열된 자료구조를 의미하며, 실생활에서는 비어있는 프링글스 통에 비유할 수 있다. push를 통해 요소를 삽입하고, pop을 통해 제거할 수 있는데, 이때 push는 파이썬 내장 함수인 append를 사용하여 리스트 안에 추가할 수 있고, pop은 내장함수 pop을 통해 요소를 제거할 수 있다. 이때 append는 가장 마지막에 추가되고 pop은 가장 마지막 요소를 꺼내고 리스트에서 삭제한다.
해당 자료구조의 특성?
: 자료간의 관계가 1대1의 선형 관계를 갖는다. 자료를 삽입(push)하거나 스택에서 자료를 꺼낼 수(pop) 있다. 이때, 마지막에 삽입한 자료를 가장 먼저 꺼내는 후입선출(LIFO) 특성을 갖고 있다.
해당 자료구조를 사용했을 때 값과 결과의 진행 과정 설명:
@@@@@@@@@@@@@@
중복문자 지우기에서는 스택이라는 자료구조를 사용하는 것이 좋습니다.
스택이란 데이터를 후입선출(LIFO=last in first out)이며 가장 늦게 들어온 데이터가 가장 먼저 나감을 의미합니다.
스택은 선형구조를 띄고있으며 데이터를 삽입하거나 빼낼 수 있습니다.
예를들어 설거지한 컵을 차곡차곡 쌓고 위에서부터 꺼내 쓰는 것이라고 생각하면편합니다.
자료구조와 연산에 대한 이해가 필요한데,
자료를 선형으로 저장할 저장소, 즉 스택 저장소가 필요하고 스택에서 가장 마지막 삽입된 데이터 위치를 top이라고 합니다.
연산의 경우 삽입과 삭제가 있는데, 삽입은 push라고 불리며 파이썬에서는 append()함수를 통해 삽입이 가능합니다. 삭제는 pop이라고 불리며 파이썬에서도 pop()함수를 사용하여 늦게 들어온 데이터부터 삭제합니다. 스택이 비어있는지 확인하는 연산은 isEmpty, 파이썬에서는 len()함수를 사용하여 데이터 유무를 확인 할 수 있습니다.
중복문자 제거는 데이터 하나하나를 stack 저장소에 삽입하다가 stack의 peak 데이터와 삽입될 예정인데이터가 같다면 제거하면 되는 것이므로, pop()을 통해 중복된 문자를 제거해주면 됩니다.
예를들어 스택이 비어있고 문자가 들어온다면 stack에 추가,
스택이 비어있지 않고 문자가 들어왔지만, peak 문자와 삽입될 문자가 다르다면 그대로 stack에 추가
스택이 비어있지 않고 문자가 들어왔을 때, peak 문자와 삽입될 문자가 같다면 stack의 peak를 pop()을 통해 제거합니다.
모든 문자를 확인했다면 stack에 남아있는 데이터를 확인합니다.
