전체 글
-
백준(BOJ) 1987번 알파벳알고리즘 풀이/백준(Boj) 2019. 8. 4. 17:50
문제 : https://www.acmicpc.net/problem/1987 문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 나의풀이: 기존 전형적인 DFS에 alphabet 배열을 매개 변수로 받아서 같은 알파벳이 나왔을 경우에는 가지 못..
-
백준(BOJ) 1019번 책 페이지알고리즘 풀이/백준(Boj) 2019. 8. 3. 23:33
문제: https://www.acmicpc.net/problem/1019 문제지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 풀이: // 처음 시도 시간 초과 #include #include using namespace std;int N;int check[10];int main(){ios_base::sync_with_stdio(0);cin.tie(0);memset(check, 0, sizeof(check));cin >> N;for (int i = 1; i > n;solve(1, n, 1);for (int i = 0; i < 10; ++i)cout
-
백준(BOJ) 1449번 수리공 항승알고리즘 풀이/백준(Boj) 2019. 8. 3. 03:21
문제: https://www.acmicpc.net/problem/1449 문제항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.항승이는 길이가 L인 테이프를 무한개 가지고 있다.항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능..
-
감시 카메라 설치알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 3. 02:18
문제 : https://algospot.com/judge/problem/read/GALLERY 코드( C ++ ) 종만북 참조 문제전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 프로게이머의 얼굴로 합성하겠다는 것입니다. 미술관의 관장을 맡고 있는 재하는 이와 같은 사태를 방지하기 위해 감시 카메라를 설치하기로 마음먹었습니다. 미술관은 여러 개의 갤러리와 이들을 연결하는 복도로 구성되어 있으며, 한 갤러리에 감시 카메라를 설치하면 이 갤러리와, 복도로 직접 연결된 갤러리들을 감시할 수 있습니다. 모든 갤러리를 감시하기 위해 필요한 최소 감시 카메라의 수는 몇 개일까요?미술관은 한 번 관람한 갤..
-
변화하는 중간 값알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 1. 01:49
문제 : https://algospot.com/judge/submission/recent/ 문제한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다.한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요. 예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다. 코드 ( C ++ ) 종만북 참조 #include #include us..
-
백준(BOJ) 10989번 수 정렬하기 3알고리즘 풀이/백준(Boj) 2019. 7. 31. 15:03
문제: https://www.acmicpc.net/problem/10989 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 나의 풀이: 시간복잡도 N을 요구하고 범위가 1~10000으로 정해져 있으니 기수 정렬을 통하여 크기를 기준으로 개수를 세주면 된다. printf와 scanf로 입력을 받아줘서 시간을 줄이자 코드 ( C++ ) #include using namespace std; int mycount[10000];int N;int main(){ scanf("%d", &N);for (int i = 0; i < N; ++i){int num;scanf("%d", &num);// 0부터 시작이므로 num-1 인덱스를 1 추가 한다.mycount[num-1]++;}for (i..
-
백준(BOJ) 1431번 시리얼 번호알고리즘 풀이/백준(Boj) 2019. 7. 31. 14:32
문제 : https://www.acmicpc.net/problem/1431 문제다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.A와 B의 길이가 다르면, 짧은 것이 먼저 온다.만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 ..
-
백준(BOJ) 1181번 단어 정렬알고리즘 풀이/백준(Boj) 2019. 7. 31. 13:38
문제: https://www.acmicpc.net/problem/1181 문제알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터길이가 같으면 사전 순으로 나의풀이 : 1. string 배열을 만들어 담는다2. size를 기준으로 정렬 한다 + 길이가 같을시 사전순으로 정렬 compare 만든다.3. unique를 통해 중복을 제거 해준다. unique에 관한 설명은 www.cppreference.com에 가셔서 검색하시면 보다 자세히 알 수 있습니다. cppreference.com 코드 ( C++ ) #include #include #include #include using namespace std; int N;bool compare..