본문 바로가기

알고리즘5

알고리즘 | Java 백준[Silver I] 스타트와 링크 - 14889 [Silver I] 스타트와 링크 - 14889문제 링크 성능 요약메모리: 15176 KB, 시간: 268 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 9월 15일 17:46:41문제 설명오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. S.. 2024. 9. 15.
알고리즘 | Java 백준[Silver III] 다음 순열 - 10972 [Silver III] 다음 순열 - 10972문제 링크성능 요약메모리: 20068 KB, 시간: 224 ms분류조합론, 수학제출 일자2024년 9월 14일 02:22:06문제 설명1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1입력첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.출력첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전.. 2024. 9. 14.
알고리즘 | Java 백준[Silver II] 키로거 - 5397 [Silver II] 키로거 - 5397문제 링크성능 요약메모리: 209904 KB, 시간: 540 ms분류자료 구조, 연결 리스트, 스택제출 일자2024년 9월 8일 00:45:54문제 설명창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.입력.. 2024. 9. 8.
알고리즘 | Java 백준[Silver II] 참외밭 - 2477 [Silver II] 참외밭 - 2477문제 링크성능 요약메모리: 11568 KB, 시간: 64 ms분류기하학, 구현, 수학제출 일자2024년 8월 24일 18:30:20문제 설명시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다.. 2024. 8. 24.
알고리즘 | 점화식과 알고리즘 복잡도 분석 점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 자기호출을 사용하는 함수의 복잡도를 구하는데 유용하게 쓰인다. 병합 정렬의 수행 시간 수행시간의점화식 T(n) = 2T(n/2) + 오버헤드 크기가 n인 병합 정렬 시간은 크기가 n/2인 병합 정렬을 두 번하는 시간과 나머지 오버헤드(두 개 정렬 결과를 병합하는 시간)를 더한 시간이다. 점화식의 점근적 분석 방법 1. 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법 2. 추정후 증명 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 3. 마스터 정리 형식에 맞는 점화식의 복잡도를 바로 알 수 있다. 반복 대치 예시 1: 팩토리얼 C부분이 오버헤드라고 할 수 있다. 예시 2 해당 크기 만큼(n) 오버헤드.. 2023. 9. 12.