백준
-
백준(BOJ) 7562번 나이트의 이동알고리즘 풀이/백준(Boj) 2019. 8. 6. 03:26
문제 : https://www.acmicpc.net/problem/7562 문제체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 나의 풀이: 큐에 pair 를 통하여 앞에 값에는 y값과 x값을 , 뒤에 값은 이동 횟수로 지정하여 0을 넣고 1씩 증가하여 도착 시 이동 횟수를 저장 하였다. 코드 ( C++ ) #include #include #include #include using namespace std; int l;int x, y, dx, dy; // 나이트의 이동 방향int my[8] = { 2,1,-2,-1,-1,-2,1,2 };int mx[8] = ..
-
백준(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이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능..
-
백준(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..
-
백준(BOJ) 1966번 프린터 큐알고리즘 풀이/백준(Boj) 2019. 7. 30. 19:27
문제 : https://www.acmicpc.net/problem/1966 문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.예를 ..