개발자 퉁이리

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 브루트포스 알고리즘 플로이드-와샬 ⊙ 문제 접근 과정 플로이드 와샬을 통해 문제를 풀었다. 먼저 길 없음을 표시하고 입력을 통해 주어진 M개의 길을 뚫어준다. 그다음 플로이드 와샬 알고리즘을 통해 거쳐가는 값이 존재하면 갱신! 그리고 2중 for문을 통해 브루트포스를 구현했다. 배열 v를 만들고..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 바로 전 단계인 11탄에서 비내림차순의 조건을 충족하기 위해 num 변수만 추가해줬다. ⊙ 문제 풀이 #include #include #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; set ..

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 이전 단계인 10탄에서 방문 여부만 제거해줬다! 왜냐하면 같은 수를 여러 번 골라도 되기 때문에. 하지만 같은 수를 여러번 골라도 같은 수열은 출력하지 않는다. set 덕분에 ㅎㅎ ⊙ 문제 풀이 #include #include #include #include using namespace std; #defi..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 비내림차순이 무엇인지 알고 싶다면? 비내림차순에 대해서 적은 글 (N과 M 8탄)을 참고하자! 비내림차순을 구현하기 위해 9탄의 코드에서 num 변수를 추가적으로 만들어줬다.현재 값보다 높은 값만 출력할 수 있도록 하는 변수다. set을 통해 중복을 제거해줬고, visited를 통해 방문한 곳은 가지 않는..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 수열의 중복을 막기 위해 set을 사용했다. vector에 수열의 값을 저장을 M개만큼 저장하고 그 값들을 set에 저장한다. 이번 문제의 point! 이번 9탄에서는 방문처리인 visited을 사용하지 않으면 시간 초과가 발생한다. N과 M 9탄에서 드디어 방문 표시를 해야 하는 이유를 몸소 확인할 수 있..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 문제의 세 번째 제한조건을 보자. 고른 수열은 비내림차순이어야 한다. 이 조건을 보고 나는 의아했다. 오름차순과 내림차순, 서로 반대말 아닌가? 그렇다는 건 비내림차순으로 나타내라면 그에 반대인 오름차순으로 나타내라는 건가? 그리고 예제 입출력을 봤다. 오름차순이다. 내 생각이 어느 정도 맞았다는 것..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 방문 여부를 체크하지 않고, 기존의 값들을 배열에 저장해 정렬했다. 그그다음 백트래킹을 통해 값을 출력해줬다. ⊙ 문제 풀이 #include #include using namespace std; #define MAX 9 int N,M; int first[MAX]; int arr[MAX]; void d..

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 문자열 ⊙ 문제 접근 과정 소문자 알파벳과 대문자 알파벳의 차이는 32 A와 Z의 차이는 25 A = '65', Z = '90' a = '97', z = '122' 이 문제의 해결 포인트! 빈도수를 저장하는 배열 alpha를 만들어줬다. 그리고 해당 알파벳의 빈도수를 0부터 25의 공간에 저장해줬다. 왜냐하면 A와 Z의 차이는 25이기 때문이다. 그리고 빈도를 저장..

https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 int로 값을 입력받지 않고 string으로 값을 입력받았다. 왜냐하면 index로 접근하고 싶었기 때문이다. 그래서 나는 index로 접근해 역으로 새로운 string에 값을 저장해주었다. 만약 두 문자열이 숫자로만 되어있을 때, 크기를 비교하고 싶으면 그냥 비교해도 문제가 없다. 따라서 숫자가 역으로 저장된 새로운 두 s..

https://www.acmicpc.net/problem/2523 2523번: 별 찍기 - 13 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 별 찍자! ⊙ 문제 풀이 #include using namespace std; int N; int main() { cin >> N; for(int i=0;i