본문 바로가기
  • 살짝 구운 김 유나

Algorithm64

Heap 힙 : 완전 이진 트리로 구현된 자료구조. 키 값이 가장 큰 노드나 가장 작은 노드를 찾을 때 사용 max heap : 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 (부모노드의 키 값 > 자식노드의 키 값) 루트노드 -> 키 값이 가장 큰 노드 min heap : 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 (부모노드의 키 값 키 값이 가장 작은 노드 힙 연산 - 삭제 >> 힙에서는 루트 노드의 원소만을 삭제할 수 있다. 1. 루트 노드의 원소 삭제 2. 마지막 노드 삭제 3. 자리 바꾸기 ( 최대힙 상태 유지) 연산을 수행할 때마다 힙 상태를 유지해야 한다. # 최대힙 # 힙 연산 - 삽입 def enq(n): global last last += 1.. 2022. 9. 13.
SWEA_5178_노드의합, SWEA_5174_subtree, SWEA_5716_이진탐색 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com SWEA_5174_subtree 문제 트리의 일부를 서브 트리라고 한다. 주어진 이진 트리에서 노드 N을 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오. 주어지는 트리는 부모와 자식 노드 번호 사이에 특별한 규칙이 없고, 부모가 없는 노드가 전체의 루트 노드가 된다. 이런 경우의 트리는 부모 노드를 인덱스로 다음과 같은 방법으로 나타낼 수 있다. 자식 노드가 0인 경우는 노드가 자식이 없는 경우이다. 입력 첫 줄에 테스트케이스의 수 T가 주어진다. 1 2022. 9. 12.
월말평가 코드 (pass) 코드 ''' 2 5 1 4 3 5 5 4 5 2 1 6 1 3 2 2 3 5 ''' T = int(input()) for test_case in range(1, T+1): # 학생수, 그룹의 최소 인원과 최다 인원 기준 # 5 1 4 N, kMin, kMax = map(int, input().split()) # 학생들의 점수 리스트 [1 2 2 3 3 5 5] S = list(map(int, input().split())) S_set = list(set(S)) # [1 2 3 5] S_set.sort() # 셋을 정렬해주기 minV = 9999999 # t1, t2 조합을 만들어 내는 이중포문 for t1 in range(len(S_set) - 1): for t2 in range(t1 + 1, len(S.. 2022. 8. 30.
SWEA_12712_파리퇴치3, SWEA_9489_고대유적 SWEA_12712_파리퇴치3 문제 N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개체 수를 의미한다. 아래는 N=5 의 예이다. 파리 킬러 스프레이를 한 번만 뿌려 최대한 많은 파리를 잡으려고 한다. 스프레이의 노즐이 + 형태로 되어있어, 스프레이는 + 혹은 x 형태로 분사된다. 스프레이를 M의 세기로 분사하면 노즐의 중심이 향한 칸부터 각 방향으로 M칸의 파리를 잡을 수 있다. 다음은 M=3 세기로 스프레이르 분사한 경우 파리가 퇴치되는 칸의 예로, +또는 x 중 하나로 분사된다. 뿌려진 일부가 영역을 벗어나도 상관없다. 한 번에 잡을 수 있는 최대 파리수를 출력하라. 제약사항 1. N 은 5 이상 15 이하이다. 2. M은 2 이상 N 이하이다. 3. 각 영역의 파리 갯수는 30 이하 이.. 2022. 8. 29.
Baekjoon_1244_스위치켜고끄기 https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. 에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다. .. 2022. 8. 28.
SWEA_13976_기지국 SS 텔레콤에서 현재 기지국의 위치와 집들이 표시된 지도를 2차원 nxn 배열로 변환하여, 기지국에 커버 되지 않는 집의 수를 찾고자 한다. 기지국은 [그림1]과 같이 세가지 종류가 있다. 각각의 기지국은 기지국이 위치한 셀에서 동서남북으로 각 1개, 2개, 3개의 셀을 커버하며, 하나의 집은 1개의 셀에 있다. 문제 주어진 2차원 배열 지도에 위치한 기지국으로 커버되지 않는 집의 수를 찾는 프로그램을 작성하시오. 제약사항 2차원 배열의 크기의 n은 50이하이다. 기지국의 수는 50이하이다. 입력 첫 줄에는 테스트 케이스의 수가 주어지고, 그 다음 줄부터 각 테스트 케이스가 n+1개의 줄로 구성된다. 테스트 케이스의 첫 줄에는 n이 주어지고, 다음 n개 줄에는 2차원 배열의 각 행이 한 줄에 차례로 주어.. 2022. 8. 28.
Baekjoon_2559_수열, Baekjoon_2491_수열 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net Baekjoon_2559_수열 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의.. 2022. 8. 28.
Baekjoon_10157_자리배정 문제 어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다. 예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. (1, 6) (7, 6) (4, 4) (7, 4) (1, 3) (6, 3) (1, 2) (1, 1) (2, 1) (3, 1) (7, 1) 이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, .. 2022. 8. 27.
Baekjoon_2578_빙고 문제 빙고 게임은 다음과 같은 방식으로 이루어진다. 먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다 다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다. 차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다. 이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다. 철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램.. 2022. 8. 27.
Tree 트리 : 비선형 구조. 그래프의 특수한 경우. 원소들 간에 계층관계를 가지는 계층형 자료구조. -> 상위 원소에서 하위원소로 내려가며 확장되는 모습 트리를 사용하는 가장 큰 이유는 문제를 해결할 때 subtree 로 나누어서 접근 할 수 있기 때문 (재귀적 정의) degree 1. 노드의 차수 : 노드에 연결된 자식 노드의 수2. 트리의 차수 : 노드의 차수 중 가장 큰 수-> 실제로 구현했을 때 공간(차원)을 미리 잡을 수 있는 정보가 된다 이진트리 : 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 - 각 노드가 자식 노드를 최대 2개 까지만 가질 수 있는 트리 특징) 1. 레벨 i 에서 노드의 최대 개수는 2^i 2. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가.. 2022. 8. 26.

티스토리툴바