본문 바로가기
반응형

알고리즘 풀이164

[백준 28068] I Am Knowledge (python) https://www.acmicpc.net/problem/28068 28068번: I Am Knowledge 저택에 살고 있는 마법사는 지하의 도서관에 자주 방문한다. 어느 날, 마법사는 도서관에 있는 책 \(N\)권을 모두 읽기로 했다. 책은 한 번에 한 권씩만 읽을 수 있지만, 책을 읽는 순서는 마음대 www.acmicpc.net I Am Knowledge 문제 마법사의 즐거움 수치에 따라 책을 다 읽을 수 있는지 없는지 판별하는 문제 정렬과 그리디를 활용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 아직 읽지 않은 책을 읽을 때 a만큼 즐거움 수치소비하고, 읽을 시 b만큼 즐거움 수치를 얻는다. 단, 즐거움 수치가 0 미만이 되면 안된다. 2. b가 a보다 큰 경우, 즐거움 수치를 얻는 형태의 .. 2023. 5. 28.
[백준 2580] 스도쿠 (python) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 문제 스도쿠를 모두 채울 수 있을 경우, 그때 가능한 경우의 수 1개 만을 출력하는 문제 백트래킹을 이용하여 해결 할 수 있었다. 📌문제 접근 포인트 1. 스도쿠에 대해서 생각해보자. 스도쿠는 가로 9칸에 숫자가 겹치면 안 되고, 세로 9칸에도 숫자가 겹치면 안 되며, 해당 3*3칸에서도 숫자가 겹치면 안 된다. 2. 유망한 조건으로 위에 3가지 조건을 만들어주자. 또, 비어있는 칸에 숫자.. 2023. 5. 21.
[백준 10798] 세로읽기 (Java) https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 세로읽기 문제 주어진 글자들을 세로로 읽어서 출력하는 문제 📌문제 접근 포인트 1. 조건을 확인하자. 조건은 5줄을 최대 15개의 단어로 이루어지게 받는다. 2. 배열을 char 타입으로 생성하자. char타입으로 해서 2차원 배열을 입력받자. 3. 앞서 받은 배열을 세로부터 출력하게 바꿔주자. 이때, char 타입의 null값은 \u0000으로 표현할 수 있다. 이걸 이용해서 출력해 보자.. 2023. 5. 17.
[백준 2212] 센서 (python) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 센서 문제 센서를 수신할 수 있는 수신 가능 영역의 합을 최소화하기 위해 기지국을 설치 시, 그때의 합을 구하는 문제 그리디 개념을 이용하여 해결 할 수 있었다. 📌문제 접근 포인트 1. 먼저 임의의 위치로 섞여 있으므로, 순서대로 파악할 수 있게 정렬해 주자. 2. 문제의 조건에 의하면 K개의 기지국을 설치한다. 즉, 센서들을 K개로 영역을 나눈다는 의미이다. 입력 예제.. 2023. 5. 16.
[백준 1157] 단어 공부(Java) https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 단어 공부 문제 알파벳 단어가 주어지면 단어에서 가장 많이 사용된 알파벳을 찾는 문제 📌문제 접근 포인트 1. 먼저 알파벳의 대소문자를 구분하지 않으나 출력은 대문자를 원하니, 대문자의 형태로 단어를 받아주자. 2. 단어 S에 존재하는 알파벳만 따로 모아주자. 이 알파벳을 이용해서, 각 알파벳 별로 존재하는 단어의 등장 갯수를 세어주자. 3. 단어별 갯수를 모은 리스트에서 최대 값을 구해주고, 이 최대값과 같은 숫자가 존재하는지 .. 2023. 5. 14.
[백준 11724] 연결 요소의 개수(python) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결 요소의 개수 문제 방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구하는 문제 BFS와 DFS를 이용해서 해결할 수 있었다. 📌 문제 접근 포인트 1. 주어진 조건대로 방향 없는 그래프(양방향 그래프)를 구성해 주자. 2. 그래프를 탐색할 수 있도록 BFS나 DFS를 구성하자. 3. 연결 요소의 개수를 구하기 위해서는 방문 표.. 2023. 5. 10.
반응형

티스토리툴바