본문 바로가기

🦄 | 코딩테스트 연습16

[Python] 백준 1068 트리 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는.. 2023. 4. 12.

[Python] 백준 23883 알고리즘 수업 - 선택 정렬 3 문제 오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구하자. N이 매우 커서 시간 초과를 고민하고 있는 우리 서준이를 도와주자. 크기가 N인 배열에 대한 선택 정렬 의사 코드는 다음과 같다. selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for last 3 1 2 4 5 (A[1..4]에서 4가 가장 크므로 교환이 발생하지 않음) -> 3 1 2 4 5 (2와 3이 교환됨) -> 2 1 3 4 5 (1과 2가 교환됨) -> 1 2 3 4 5. 총 3회 교환이 발생하고 .. 2023. 4. 12.

[Python] heapq 라이브러리 파이썬의 heapq 라이브러리에 대해서 알아보자! 1. 소개 heap 자료구조를 구현하는 내장 모듈이고 최소 힙을 기본으로 제공한다. 따라서 가장 작은 원소가 루트 노드가 된다. 2. 주요 함수들 heapify(리스트) : 리스트를 힙으로 변환 heappush(힙, 원소) : 새로운 원소 추가 heappop(힙) : 힙에서 루트 노드 제거 및 반환 heapreplace(힙, 원소) : 힙에서 루트 노드를 제거하고 새로운 원소 추가 ( pop&push 한 번에! ) nlargeset(n, iterable, key=None) : iterable 객체에서 n개의 가장 큰 원소 반환(리스트 형태) nsamllest(n, iterable, key=None) : iterable 객체에서 n개의 가장 작은 원소 반.. 2023. 4. 11.

[LeetCode] 21. Merge Two Sorted Lists (Python) - Linked List 나의 코드 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # empty list cNode = result = ListNode() while list1 and list2: if list1.val < list2.val: cNode.next = list1 list1, cNode = list1... 2023. 4. 10.

[Python] 파이썬 코딩테스트를 위한 개념 정리 방학동안 코딩테스트 공부를 하기 위해서 두고두고 볼 겸 파이썬에 관련된 간단한 개념들을 한 페이지에 정리해보았다! 입력과 출력 입력 - input() : 사용자로부터 문자열 한 줄을 입력받는다. - map() : 모든 원소에 전달한 함수 하나씩 적용한 객체 반환 # 튜플의 형태의 객체이므로 다음과 같이 언패킹 가능 a, b, c = map(int, input().split()) # list로 변환 가능 data = list(map(int, input().split())) 입력량으로 인한 수행시간 초과 오류 발생시 시스템 라이브러리에 정의된 readline() 이용 import sys str = sys.stdin.readline().rstrip() # rstrip()으로 줄바꿈 삭제 print(str) 출.. 2023. 1. 4.

[Python] 백준 1083 소트 문제 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 입력 7 10 20 30 40 50 60 70 1 예제 출력 1 20 10 30 40 50 60 70 예제 입력 2 5 3 5 1 2 4 2 예제 출력 2 5 3 2 1.. 2022. 3. 28.

[Python] 백준 1920 수 찾기 N = int(input()) Nlist = list(map(int, input().split(' '))) M = int(input()) Mlist = list(map(int, input().split(' '))) for i in Mlist: if(i in Nlist): print(1) else: print(0) 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에.. 2022. 3. 28.

[Python] 백준 1966번 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 .. 2022. 3. 28.

열혈 C_ 문자열처리 문제 문자열을 입력받았을 때 그 안에 존재하는 숫자의 총 합을 계산하기 입력 예시 A1h2#9 출력 예시 12 코드 #include #include int SSum(char str) { static int diff = 1 - '1'; return str + diff; } int main() { char str[50]; int len; int sum = 0; printf("문자열 입력: "); fgets(str, sizeof(str), stdin); len = strlen(str); for (int i = 0; i = '1' && str[i] 2022. 1. 10.

이전 1 2 다음

티스토리툴바