본문 바로가기
  • 기억의 유한함을 기록의 무한함으로✍️            예비 개발자가 꿈꾸는 공간 여기는 안나의 개발 블로그 💻

Algorithm45

[백준 Java] 9328번 열쇠 (구현, BFS) [Gold I] 열쇠 - 9328 문제 링크 성능 요약 메모리: 320872 KB, 시간: 1328 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 문제 설명 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너.. 2023. 8. 9.
[백준 Java] 2252번 줄 세우기 ( 그래프 , 위상정렬) [Gold III] 줄 세우기 - 2252 문제 링크 성능 요약 메모리: 46084 KB, 시간: 4360 ms 분류 그래프 이론, 위상 정렬 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 .. 2023. 6. 26.
[알고리즘 정리] Topology Sort ( 위상 정렬 ) - O(V+E), 순서가 정해져 있는 작업, 여러 답이 존재 Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc... 2023. 6. 26.
[백준 Java] 2751번 수 정렬하기( 정렬, 계수정렬 ) [Silver V] 수 정렬하기 2 - 2751 문제 링크 성능 요약 메모리: 134424 KB, 시간: 692 ms 분류 정렬 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 💡 나의 접근 주어진 N의 개수가 1,000,000이기 때문에 O(N^2) 시간복잡도를 가지게 되면 터지게 된다. 그래서 O(NlogN)이나 O(N) 시간복잡도를 가지는 정렬을 생각해 보아야 할 것이다. A.. 2023. 6. 26.
[알고리즘 정리] Counting Sort ( 계수 정렬 ) - O(N+k), 추가 메모리, Stable Counting Sort (계수 정렬) 이란? 계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다. 더보기 백준 문제 https://www.acmicpc.net/problem/2751 과정 과정은 간단하다. 1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기 2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기 3. 각 값의 개수를 누적으로 바꾸기 4. 뒤에서부터 자리 찾아주기 위 순서에 따라서 위 arr 배열을 정렬해보자 1. 가장 큰 값을 찾는다. ➡️ max = 5 2. 각 값의 개수를 담는다. arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다. 3. 각 값의.. 2023. 6. 25.
[백준 Java] 2579번 계단 오르기(구현, 시뮬레이션) [Silver III] 계단 오르기 - 2579 문제 링크 성능 요약 메모리: 11608 KB, 시간: 76 ms 분류 다이나믹 프로그래밍 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 .. 2023. 6. 25.
반응형