전체 글(45)
-
백준 20551번: Sort 마스터 배지훈의 후계자 (C++)
https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 풀이 처음 입력받은 배열 A의 위치를 반환하지 않아도 돼서 편하게 풀 수 있는 이분 탐색 문제. map으로 구현해도 될 것 같지만 중복된 숫자가 있어서 이분 탐색이 편한 듯 하다. left 를 배열의 첫번째 인덱스인 0, right 를 마지막 인덱스로 설정하고 탐색을 진행했다. 구해야 하는 것이 처음으로 등장한 위치기 때문에 is_possible 함수를 D 가 더 작을 때 ..
2023.01.23 -
백준 17266번: 어두운 굴다리 (C++)
https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 전형적인 이분 탐색 문제. 는 모르겠고 이분 탐색 풀고 싶어서 풀어봤다. 이분 탐색 조건인 is_possible 함수 설정을 조금 생각해야했다. mid (가로등 높이) 값을 비교해야하는 부분이 1. 0 ~ 첫 가로등 2. 가로등 사이 3. 마지막 가로등 ~ N 이렇게 존재하는데 가로등 사이는 양 쪽에서 빛을 비추기 때문에 반으로 나눠주었다. 3가지 조건을 매번 탐색하며 진행했는데 쓰면서 보니 가..
2023.01.21 -
백준 13140번: Hello World! (C++)
https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 풀이 오늘 순열로 현타오게 만든 문제. 완전 탐색인건 알고 접근했으나 무지성 for 문과 if 문을 남발하던 도중 이건 아니다 싶어서 찾아봤다. 순열로 너무 간단하게 풀리는 것을 보고 조금 충격이었다. unordered_map을 이용해 helowrd에 해당하는 value를 계속 변경하는 방법이다. 순열로 변경하기 때문에 모든 조건을 탐색할 수..
2023.01.21 -
백준 1759번: 암호 만들기 (C++)
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 순열을 이용한 조합 방법이 있어서 적용시켜봤다. vector n을 사용했는데 { 1, 1, 1, 0, 0, 0, 0 } 의 꼴로 저장한 다음 이전 순열로 돌려주면 마지막엔 { 0, 0, 0, 0, 1, 1, 1 } 이 된다. 여기서 1 에 해당하는 배열 위치의 값을 추출하면 조합이 된다. { 1, 1, 1, 0, 0, 0, 0 } { a, b, c, d, e, f, g } 여기서 부터 시작해서 {..
2023.01.21 -
백준 2309번: 일곱 난쟁이 (C++)
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 그냥 완전 탐색으로 풀어도 되지만 순열 연습용으로 풀었다. 우선 난쟁이들을 정렬하고 순열을 돌려주었다. 그리고 앞의 7명의 값을 더했을 때 100이 되면 종료시키는 방법으로 구현했다. 전체 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int Dwarf[9]; i..
2023.01.21 -
백준 10974번: 모든 순열 (C++)
https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 골드5 문제 푸는데 구현이 되게 까다로운 문제가 순열로 너무 쉽게 풀리는 것을 보고 현타와서 순열 알고리즘을 몇개 풀었다. next_permutation(v.begin(), v.end()) 을 실행하면 입력받은 배열을 바로 다음 순열로 변경한다. do while을 쓴 이유는 next_permutation(v.begin(), v.end()) 실행 시 배열을 변경시키기 때문이다. 정렬된 배열을 한번 출력하기 위해 사용했다. 전체 코드 #include #include #include u..
2023.01.21