본문 바로가기
반응형

분류 전체보기1067

BOJ 15665 : N과 M (11) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15665  같은 수를 여러번 골라도 되기 때문에 중복되는 입력은 큰 의미가 없다.중복되지 않은 총 수를 count하여 N을 바꾸자.이때, N과 M (10)과 달리, possible은 중복을 체크하는 용도로만 사용한다.int count = 1;for (int i = 1; i  N이 변경되었으므로, visit관련 코드는 모두 필요가 없다.#include int N, M;int list[10];int possible[10000 + 100]; /* 가능한 번호의 수 10000 */int input[10]; /* input 저장 */void outputList(){ for (i.. 2021. 2. 23.
BOJ 15664 : N과 M (10) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15664  다음 Level의 숫자가 크거나 같아야 하므로, start를 추가하기만 하면 된다.N과 M(2)와 N과 M(9)를 참고하자.#include int N, M;int list[10];int visit[10];int possible[10000 + 100]; /* 가능한 번호의 수 10000 */int input[10]; /* input 저장 */void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } }.. 2021. 2. 23.
BOJ 15663 : N과 M (9) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15663  N과 M의 응용 버전이다.N과 M (5)에서 visit 배열을 이용해 번호를 사용했는지 체크했다면, 이제는 visit을 counting해서 가능한 수까지 사용하도록 바꾸면 된다. 예제 입력 2를 보자.4 29 7 9 1 9가 2개, 7이 1개, 1이 1개 있다. 즉, 9는 최대 2번까지 visit으로 카운팅 할 수 있다.따라서 possible 배열을 만들어서, possible[9] = 2를 저장해두자.9를 사용하였다면, visit[9]++가 되고, 1 = visit[9] != possible[9] = 2가 되므로, 9를 한번 더 사용할 수 있게 된다. 이때,.. 2021. 2. 23.
BOJ 15657 : N과 M (8) - 중복 조합 combinations with repetition SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15657  N과 M (5)와 마찬가지로 input에 대해서 N과 M (4)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0, 1); return 0;} 2021. 2. 22.
BOJ 15656 : N과 M (7) - 중복 순열 permutations with repetition A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15656  N과 M (5)와 마찬가지로 input에 대해서 N과 M (3)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0); return 0;} 2021. 2. 22.
BOJ 15655 : N과 M (6) - 조합 combination SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15655  N과 M (5)와 마찬가지로 input에 대해서 N과 M (2)의 코드를 조금만 수정하면 된다.#include int N, M;int list[10];int input[10];void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; input[k] = tmp; } } } DFS(0, 1); return 0;} 2021. 2. 22.
BOJ 15654 : N과 M (5) - 순열 permutation A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/15654   N과 M (1)은 1~N으로 순열을 출력했다면, 이번엔 특정 input에 대해서 순열을 출력하면 된다. 사전 순으로 증가하는 순서로 출력해야 하므로, input을 입력받고 정렬하자.N이 작기 때문에 단순한 O(N2) 정렬로 해도 큰 무리가 없다.#include int N, M;int list[10];int visit[10];int input[10]; /* input 저장 */void outputList(){ for (int i = 0; i input[k]) { int tmp = input[i]; input[i] = input[k]; i.. 2021. 2. 22.
BOJ 14891 : 톱니바퀴 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/14891  시뮬레이션 문제는 시키는대로 구현하면 된다.이 문제는 연속으로 회전이 발생하므로, DFS로 연속 회전 시켜보자. 먼저 rotate를 구현해보자.톱니의 번호와 방향을 입력받으면 회전하는 함수는 아래와 같이 구현할 수 있다.톱니바퀴 4개와 12시 방향 = 1 부터  8까지(순서대로 시계방향)의 톱니를 넣을 수 있는 2차원 배열을 선언하자.int wheel[5][10]; /* wheel[번호 1~4][각 톱니 1~8] */void rotate(int number, int dir){ int te.. 2021. 2. 21.
BOJ 1655 : 가운데를 말해요 with 우선순위 큐 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크알고리즘 문제 전체 링크 www.acmicpc.net/problem/1655 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리  가운데라는 값은 우선순위로 두기 굉장히 애매하다.이유는 가장 높은 우선순위의 가운데와 최악의 가운데를 정의할 수 없기 때문이다. 만약 어떤 값들 중, 가운데 값을 pop한다고 하자. 그러면 heap[hn.. 2021. 2. 21.
반응형

티스토리툴바