본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 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.
[백준 12931] 두 배 더하기 (python) https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 두 배 더하기 문제 0으로 이루어진 크기 N의 배열 A를 주어진 조건에 맞는 연산을 진행했을 때, B와 같게 만들려면 최소 몇 번 연산을 구하는 문제. 그리디로 접근해서 해결할 수 있었다. 📌문제 접근 포인트 1. 주어진 연산은 배열의 값 1개를 1 증가 & 전체를 2배 하기의 연산의 과정으로 이루어져 있다. 0으로 이루어진 A배열을 B배열로 만드는 것보단 B배열을 0으로 이루어진.. 2023. 5. 9.
[백준 2667] 단지번호붙이기 (python) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 단지번호 붙이기 문제 N * N 크기의 정사각형의 칸에 이어진 숫자 단지들의 총 개수와 각 단지의 크기를 구하는 문제 BFS개념을 활용하여 해결할 수 있었다. 📌 문제 접근 포인트 1. 마을의 수를 탐색하고, 이어진 칸을 확인하는 것이므로 너비 탐색(BFS)을 이용하여 탐색을 진행해 주자. 2. 방문처리와 탐색을 동시에 진행하고, 리스트를 하나 만들어줘서 탐색하면서 세어준 개수를 넣어주자. 또 진행.. 2023. 5. 7.
[백준 1541] 잃어버린 괄호(python) https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 잃어버린 괄호 문제 +와 -로 이루어진 숫자 계산식에 괄호를 쳐서 값을 최소로 만드는 문제 단순 계산 아이디어를 떠올려서 split을 이용해 풀 수 있었다. 📌문제 접근 포인트 1. +와 -로 이루어진 숫자 계산식에 괄호를 쳐서 최솟값을 만들려 한다는 건 즉 - 사이의 숫자들을 모두 더해서 빼주면 된다는 뜻이다. 예를 들어 25-20+15-5+10+15 이런 숫자가 있다면 최소로 만들어주려면.. 2023. 5. 7.
반응형

티스토리툴바