본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 2023번 : 신기한 소수 답 www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 간단한 backtracking문제였습니다. 풀이방법 1. 소수인지 판단 소수라면 다음 단계로 간 후 이전 수 * 10 + 1~9까지 대입해서 소수인지 판단 2. depth(n-1)까지 도달했다면 답 vector에 push Code #include #include using namespace std; vector ans; bool isPrime(int num){ for(int i = 2; i*i > ..
(C++) - 백준(BOJ) 2110번 : 공유기 설치 답 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 해석이 좀 난해한 이분탐색 문제였습니다. 풀이방법 * 최대한 공유기를 넓게 c만큼 설치했을 때는 집이 각 공유기가 설치된 위치에 위치하고 있습니다. * 최대한으로 설치하기 위해서는 첫번째 집에 공유기를 설치하면서 시작하는 것이 좋습니다. 1. 집의 좌표를 오름차순으로 정렬 2. 첫째 집을 제외한 모든 집의 좌표에 대해 공유기 두 개 사이의 거리가 x이..
(C++) - 백준(BOJ) 15686번 : 치킨배달 답 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 비트마스킹을 이용해 m개 이하의 치킨집을 연 후 치킨거리를 게산하여 최솟값을 출력하는 문제였습니다. 풀이방법 시간복잡도 : (살릴 치킨집을 고르는 시간) * (다 고른 후 도시의 치킨 거리를 구하는 시간) = (2^m) * n^2 1. n^n의 격자에서 입력 받을 때 집의 좌표와 치킨집의 좌표를 각자 저장합니다. 2. 비트마스킹을 이용해 치킨집이 열려있는 상태를 표시할 수 있습니다. 2-1..
(C++) - 백준(BOJ) 17219번 : 비밀번호 찾기 답 www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번�� www.acmicpc.net map을 이용해 간단히 풀 수 있는 문제였습니다. 풀이방법 1. map에 site주소와 비밀번호를 key,value 쌍으로 저장합니다. 2. n만큼 찾고자하는 site주소를 key로 접근하여 value를 출력해주면 답이 됩니다. Code #include #include #include using namespace std; int main(){ map siteInfo; int m..
(C++) - 백준(BOJ) 9020번 : 골드바흐의 추측 답 www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 아리스토테네스의 체를 이용해 푸는 문제였습니다. 풀이방법 1. 아리스토테네스의 체로 소수가 아닌 수들을 체크한다. 2. 서로 다른 두 소수들 중 가장 작은 차이가 나는 경우는 두 소수가 각각 n/2일 경우다. 따라서 차이가 가장작은 n/2를 중앙으로 i, n-i를 차례대로 보면서 정답을 갱신해나가면 차이가 최소인 두 소수가 나온다. Code #include #define fastio ios_..
(Javascript) - 백준(BOJ) 11005번 : 진법 변환 2 www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 �� www.acmicpc.net 진법을 변환해보는 문제였습니다. 풀이방법 1. parseInt함수로 10진수로 입력된 문자열을 parseInt로 만들어주고 나온 결과를 toString함수에 넣어 b진수로 변환한 결과를 저장합니다. 2. 그 결과의 길이만큼 loop를 돌며 출력하는데 알파벳 소문자에 해당하는 부분이 나오면 toUpperCase함수를 사용해 대문자로 수정해서 출력해줍니다. Code process.stdin.resume(..
(C++) - 백준(BOJ) 11561번 : 징검다리 답 www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이분탐색문제였습니다. 풀이방법 1. 최대의 징검다리를 밟을 경우는 무조건 이전거리보다 1만큼만 더 뛰는 것입니다. 따라서 매번 뛰는 횟수들을 계산했을 때 1의 등차를 가진 수열의 형태로 뛸 거리가 정해집니다. 징검다리 개수를 m개라고 했을 때 m(m+1)/2 > n; cout
(Python) - 백준(BOJ) 5052번 : 전화번호 목록 답 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 문자열을 다루는 문제였습니다. 풀이방법 문자열을 사전순으로 정렬한 후 i+1번쨰에 있는 문자열에서 i가 있는 것을 확인만 한다면 O(n)만에 일관성 여부를 검사할 수 있습니다. 마지막으로 접두사의 의미를 정확히 알아야합니다. 만약 전화번호 목록에 211, 11211 이런식으로 있다면 11211에 211이 포함이 되어있음에도 접두사가 아니므로 일관성이 있습니다. YES를 출력해야하나 ..

티스토리툴바