본문 바로가기

Algorithm/Greedy Algorithm

Baekjoon 1543 문서 검색 2019. 6. 2. Link https://www.acmicpc.net/problem/1543 소스결과 1988 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘, 문자열 처리, 탐색 설명 영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자. 문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다. 이번 문제는 String 클래스의 find와 indexOf 함수를 합쳐놓은(?) 방식으로 풀었다. 알고리즘 1. 총 문자열과, 검색할 문자열을 입력 받는다. 2. 0번 인덱스부터 문자열을 비교한다. 2-1. 현재 탐색하는 문자열의 위치와, 탐색할 문자..
Baekjoon 1946 신입 사원 2019. 6. 2. Link https://www.acmicpc.net/problem/1946 소스결과 2888 KB / 144 ms 언어 C++ 17 출처 Baekjoon, ACM-ICPC 2006 분류 그리디 알고리즘 설명 한 지원자의 서류 심사 성적과, 면접시험 성적중 적어도 다른 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 하에 지원자를 선발할 때 선발 할 수 있는 최대 인원 수를 구하여라. 되게 간단한 듯 보이면서 많이 틀렸던 문제다. 서류 심사 성적을 기준으로 정렬을 한 뒤, 면접 시험에 대해서 처리 하는 부분이 애매했었다. 결과론적으로 서류 심사 성적이 같다면 면접 시험 성적이 좋은 사람을 위로 놓았다. 또한 서류심사 성적이 낮지만, 면접 시험 성적이 가장 좋은 경우도 존재 할 수 있기 때문에, ..
Baekjoon 2217 로프 2019. 6. 2. Link https://www.acmicpc.net/problem/2217 소스결과 3276 KB / 16 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘 설명 k개의 로프 정보가 주어질 때, 로프를 사용하여 들어 올릴 수 있는 최대 중량을 계산하여라. 알고리즘에 있어 크게 생각할 부분은 없었다. 각 로프 입장에서는 자기가 들 수 있는 값보다 큰 값을 들어올리지는 못하기 때문에 자기 자신을 기준으로 자기보다 많이 들어 올릴 수 있는 수 만큼을 곱해주면 그 로프를 이용 했을 때의 최대 중량이 된다. 최대 값만 찾으면 되기에 배열을 이용해도 되지만 이번 문제에서는 힙을 이용했다. 힙은 최대 힙으로 사용하고, 정렬된 값을 넣을 때에는, (자신의 장력) * (남은 로프의 수)의 값으로 넣어준다..
Baekjoon 1931 회의실 배정 2019. 6. 2. 링크 https://www.acmicpc.net/problem/1931 소스결과 2772 KB / 32 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘 설명 한개의 회의실과 회의 일정이 주어질 때 회의가 겹치지 않게 최대한 많이 배정 할 수 있는 수를 구하여라. 문제 자체에서 그리디 알고리즘이라는걸 알 수 있는 문제였다. 정렬을 이용하면 쉽게 해결 될 꺼 같은 문제 였는데 감이 잡히지 않아 고생좀 했었다. 종료 시간을 기준으로 정렬을 하되, 종료 시간이 같은 경우 시작시간이 작은 경우로 정렬 하면 된다. 정렬 후 최선의 경우를 선택 하면서 다음에 시작이 가능한 시간만 골라서 이어서 카운팅 해주면 정답이 된다. 알고리즘 1. 종료시간을 기준으로 경우의 수를 정렬한다. 단 종료시간이 같은 ..
Baekjoon 1080 행렬 2019. 4. 1. Link https://www.acmicpc.net/problem/1080 소스결과 1992 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 그리디 알고리즘 설명 0과 1로 이루어진 행렬 A B에 대해서 특정 연산을 통해 A를 B로 바꾸는 연산의 최솟값을 구하는 프로그램을 만들자. 처음에는 이 문제가 왜 그리디 알고리즘인지 궁금했다. 질문 게시판에는 이미 같은 생각을 가진 다른사람이 있었다. 0,0을 뒤집을 수 있는 경우는 0,0에서 연산을 하는 경우밖에 없다. 따라서 특정 위치는 뒤집을 수 있는 경우의 수가 9보다 작은 경우가 존재한다. 0,0 부터 가로로 확인하면서 뒤집는 수와, 세로로 확인하면서 뒤집는 수를 구해, 둘중에 한군데라도 가능하다면 결과값을 비교해 출력한다. 알고리즘 1. ..
Baekjoon 1541 잃어버린 괄호 2019. 3. 8. Link https://www.acmicpc.net/problem/1541 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 그리디 알고리즘 설명 양수, +, -로 구성된 식에 적절한 괄호를 추가해 결과 값을 최소로 만드는 경우의 값을 출력한다. -가 등장하는 순간 그 뒤에 + 식을 전부 괄호로 묶으면 괄호 안의 결과 값을 빼는 모습이 된다. 즉 -가 등장하기 전 까지의 합과, 등장한 후의 합을 빼면 그 결과 값은 항상 최소값이 된다. 굳이 어려운 점을 따지자면 문자열을 입력받아 연산자와 피연산자를 나누는게 어려운부분..? 알고리즘 1. 문자열을 입력받는다. 2. 문자열의 0번 인덱스부터 문자열의 길이만큼 반복한다. 2 - 1. 현재 위치의 문자 값이 숫자인 경우 연산자를 ..
Baekjoon 1049 기타줄 2019. 1. 16. Link https://www.acmicpc.net/problem/1049 소스결과 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 그리디 알고리즘 설명 최대 100줄짜리 기타를 치시거나 6현 기타 17개를 동시에 치실줄 아시는 세계적인 기타 플레이어 김지민씨가 새로운 줄을 사거나 교체 해야할 때 가장 싸게 사면 얼마에 살 수 있는지 대신 계산해주는 코드를 작성하자 경우는 크게 2개로 나눌 수 있다. 1. 낱개 가격으로 6개를 사는게 패키지보다 가격이 싼 경우 2. 패키지로 사는게 더 싼 경우 따라서 2가지 경우의 최소 값만 구하면 된다. 배열 전체를 저장하지 않아도 된다. 패키지 가격의 최소값과, 낱개 가격의 최소 값만 구하면 된다. 6개가 넘어가는 경우를 먼제 구한후 나머지 줄..
BaekJoon 2875 대회 or 인턴 2019. 1. 16. Link https://www.acmicpc.net/problem/2875 소스결과 1984 KB / 0 ms 출처 Backjoon, COCI 2010/2011 Contest #1 1번 언어 C++ 17 분류 그리디 알고리즘 설명 백준대학교에서는 총장님의 권력이 막강해 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는데 올해는 인턴십 때문에 사람을 빼야한다. 최대한 사람좀 많이 남겨보라는 총장님의 지시를 이행하는 문제 최대가 100번이기에 반복문을 사용해도 괜찮다. 생각을 그대로 옮기면 되는 문제. 잉여 인원을 먼저 인턴십에 다 보낸 후, 동시에 2명씩 줄여나가면 되는 문제다. 여러 경우로 나눠서 nested-if 문을 사용해 풀어보려 했으나 생각보다 코드가 길어져서 while문을 통해 반복 하는 형..

티스토리툴바