백준 - 알고리즘 수업 - 점근적 표기 1 15650번 [6일차]시간제한메모리 제한1초512MB문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다. 입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 나의코드package day6;import java.util.Arrays;import java.util.HashSet;import java.uti..
jjuya
알고리즘 수업 - 점근적 표기 1 24313번 [6일차]시간제한메모리 제한1초512MB문제오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. 입력첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다...
백준 - N과 M (1) 15649번 [6일차]시간제한메모리 제한1초512MB문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 설명 [알고리즘] 백트래킹백트래킹현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘어떤 노드의 '유망성'을 판단한뒤, 해당 노드가 유망라지 않으면 부모 노드로 돌아가 다른 자식 노..
힙(Heap), 우선순위 큐(Priority Queue)Heap이란?완전이진트리 형태의 자료구조우선순위큐를 구현하기 위해 사용되는 자료구조여러개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다 힙(Heap) : 특정 규칙을 갖는 완전 이진트리최대힙 :부모 노드가 자식 노드보다 항상 크거나 같음최소힙 : 부모 노드가 자식 노드보다 항상 작거나 같음이진트리각 노드가 최대 두개의 자식 노드를 가지는 트리 구조완전 이진 트리 : 말단 노드를 제외하고 모든 노드가 2개의 자식을 갖고있는 이진트리 우선순위 큐우선순위 큐란?Queue는 먼저 들어온 데이터가 나가는 FIFO(선입선출) 형식의 구조우선순위 큐(Priority Queue)는 들어온 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조우선순..
백트래킹현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘어떤 노드의 '유망성'을 판단한뒤, 해당 노드가 유망라지 않으면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성만 있는 경우의 수만 찾아보는 방법가능한 모든해를 탐색하면서 유효하지 않은 해가 나오면 되돌아가 다른 해를 찾음재귀를 사용하며, 가지치기(Plunning)을 통해 효율성을 높임해 공간이 매우 커서 전체 탐색이 어려운 탐색문제, 최적화 문제, 제약조건 문제 등에 적용 간혹, 브루트포스와 백트래킹, dfs를 혼동하는 경우가 있다.브루트포스는 '모든 경우의 수' 를 찾아보는것장점은 모든 경우의 수를 탐색하다보니 만족값을 100%찾아낸다하지만 단점은 모든 경우의 수를 판단하는 만..
백준 - 인사성 밝은 곰곰이 25192번 [5일차]시간제한메모리 제한1초1024MB문제알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자! 입력첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 N 이 주어진다...
백준 - 숫자카드2 10816번 [5일차]시간제한메모리 제한1초256MB문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되..
백준 - 숫자카드 10815번 [5일차]시간제한메모리 제한2초256MB문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할..
백준 - 알고리즘 수업 - 알고리즘의 수행 시간 6 24267번 [5일차]시간제한메모리 제한1초512MB문제오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) { sum 입력첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다. 출력첫째 줄에 코드1 의 수행 횟수를 출력한다.둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3..
백준 - 알고리즘 수업 - 알고리즘의 수행 시간 4 24265번 [5일차]시간제한메모리 제한1초512MB문제오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) { sum 입력첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다. 출력첫째 줄에 코드1 의 수행 횟수를 출력한다.둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 ..
