본문 바로가기

알고리즘6

파이썬PS) 백준 14729 칠무해 - 최대힙 사용 파이썬PS) 백준 14729 칠무해 - 최대힙 사용 문제 링크 : https://www.acmicpc.net/problem/14729 제출 코드: https://www.acmicpc.net/source/45496454 14729번: 칠무해 조(Joe)는 중앙대학교 교수이고, 논리회로 설계 과목을 담당하고 있다. 그는 수업을 하면서 7명의 학생을 제외한 나머지 학생들에게 좋은 학점을 주겠다고 약속을 하였다. Joe 교수님을 돕기 위해 www.acmicpc.net 0. 파이썬으로 풀 경우 단순하게 모든 입력값을 리스트에 append 하고 정렬하여 7개만 출력하는 방법으로도 제한시간내에 통과된 제출이 있었다. 그러나 학생 수의 입력 범위가 최대 10,000,000으로 매우 크고 출력 값은 최솟값 7개만 필요했.. 2022. 7. 4.
파이썬PS) 백준 6603 로또. 백트래킹 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 파이썬 PS) 백준 6603 로또. 백트래킹 알고리즘 - dfs를 이용한 백트래킹 1. 코드 1 import sys 2 3 while True: 4 nums = list(map(int, sys.stdin.readline().split())) 5 if nums[0] == 0: 6 break 7 8 nums.pop(0) 9 V = 6 10 stack = [] 11 12 13 def dfs(.. 2022. 4. 12.
개발일지_9) 백준 골드 달성. 자료구조가 너무 재밌어서 큰일😆😆 1. 백준 티어 골드를 달성했다. 처음으로 문제 푼 날 기준으로는 약 5개월. 코딩을 처음 해본 날 그러니까, html 문서에 hello world를 찍은 날 기준으로는 약 8개월. 배경지식 없이 시작한 것 치고는 꽤 빠른 편이지 않을까..? 2. 요즘 자료구조가 너무 재밌다. 자료구조란 말을 처음 들은 순간을 기억한다. java에서 원시 타입과 참조 타입의 차이에 대한 수업 내용이었다. 여기서 처음으로 스택과 힙이라는 용어를 배웠다. 그 뒤론 그래프 문제 해결을 목표로 공부하면서 자연스레 하나씩 찾고 이해하고 사용하게 되었고. 그래프를 코드로 표현하는 방법을 깨우치니까 갑자기 dfs, bfs, 재귀, DP, 백트래킹 등등의 알고리즘 기법들의 코드가 눈에 들어오기 시작했다. 백준 골드 달성의 1등 공신 .. 2022. 4. 12.
파이썬PS) 백준 7568 덩치 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 아이디어: 문제에 큰 힌트가 숨겨져 있다. '만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다' 사람 한 명씩 전체 리스트를 순회하면서 자신보다 큰 사람이 아무도 없으면 1등이고, 자신보다 큰 사람이 한 명씩 증가할 때마다 등수가 +1 씩 증가한다. N의 최댓값이 50 이므로 시간 복잡도 O^2의 이중 for 문을 이용해도 큰 부담이 없다. 몸무게와 .. 2022. 3. 29.
파이썬) 객체 리스트의 다중 정렬 (백준 10825) students.sort(key=lambda x: (-x.native_lang, x.english, -x.math, x.name)) 객체 리스트 정렬 방법에 관한 정보만을 바로 보려면 아래 3번 문단으로 클래스로 찍어낸 객체들을 배열한 리스트에서, 객체의 여러 속성을 기준 삼아 정렬하는 알고리즘을 익히기 좋은 문제가 있어 정리. (물론 문제만 해결하자면 객체를 만들지 않고 2차원 배열을 이용하는 방법이 더 간단하다) https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거.. 2022. 3. 27.
자바) 백준 4948번: 베르트랑 공준 백준 4948번: 베르트랑 공준 (https://www.acmicpc.net/problem/4948) 소수 문제이다. 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구한다. '에라토스테네스의 체 '를 사용 할 수 있다면 복잡하지 않게 풀 수 있다. 순서) 에라스토테네스 체 작성 -> 체 메서드를 이용하여 2부터 2n 까지의 소수 여부가 기록된 boolean 배열 생성 -> n+1 부터 배열 끝까지 소수를 확인 -> count++조건이 n 보다 커야 하므로 n은 포함시키기 않음. 전체코드 package backJoonQ2022year; import java.io.BufferedReader; import java.io.IOException; import java.io.Input.. 2022. 2. 18.