본문 바로가기
반응형

알고리즘312

BOJ 5896 : 효율적으로 소 사기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5896 우선순위 큐를 이용하여 문제를 풀 수 있다. 아래의 경우에 대해서 생각해보자. 1) 쿠폰을 사용할 수 없는 경우. 모든 소의 원가에 대해 가장 가격이 낮은 소부터 산다. 2) 모든 소에 대해 쿠폰을 사용할 수 있는 경우. 모든 소의 쿠폰 적용가에 대해 가장 가격이 낮은 소부터 산다. 두 경우는 쉽게 해결할 수 있다. 문제는 쿠폰의 수가 0 < K < N인 경우이다. 쿠폰을 사용하였을 때, 가격이 가장 작은 소부터 고르고, 남은 소 중에는 원가에서 가장 싼 가격만 고를 경우 아래와 같은 문제가 생길 수 있다. 먼저 돈이 7원, 쿠폰은 1장만 쓸 수 있는 경우를 보자. 소1 : 원가 - 10원, 쿠폰가 - 5원 소2 .. 2021. 5. 18.
SWEA 2105 : 디저트 카페 (모의 SW 역량테스트) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 디저트 카페 링크  MAP의 좌표는 (1, 1)부터 시작하도록 입력을 받는다.int T, N;int MAP[MAX][MAX];void input(){ scanf("%d", &N); for (int r = 1; r  움직일 수 있는 길은 오른쪽 아래부터 시작하여 시계 방향이므로, dr, dc를 잘 mapping 시킨다.반드시 시계 방향으로 정의해야 한다./* 순서대로 오른쪽 아래, 왼쪽 아래, 왼쪽 위, 오른쪽 위 */int dr[] = { 1, 1, -1, -1 };int dc[] = { 1, -1, -1, 1 }; 매 tc마다 dir = 0 (오른쪽 아래)부터 시계 방향으로 길을 잘 만들어.. 2021. 5. 17.
SWEA 2112 : 보호 필름 (모의 SW 역량테스트) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 보호 필름 문제에서 요구한 대로 약품을 투입한다.이 때, DFS에서 매번 MAP을 copy하는 비용을 낮추기 위해 약간의 테크닉을 사용할 수 있다.특성 A가 0, B가 1이므로, MAP[1]에는 0을, MAP[2]에는 1을 저장해둔다.int MAP[3][MAX][MAX];int list[MAX];void input(){ scanf("%d %d %d", &D, &W, &K); for (int r = 1; r  이렇게 해두고, list에는 약품을 투입하지 않을지, A를 투입할지, B를 투입할지를 DFS로 만들면 된다.따라서 성능검사를 통과하는지 check하는 함수는 아래처럼 만들 수 있다.l.. 2021. 5. 14.
BOJ 2503 : 숫자 야구 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2503 숫자 야구의 원리는 삼성 B형 샘플 문제 : 숫자야구게임을 참고하자. 이 문제에서는 답이 되는 answerList 배열에서 답이 될 수 없는 숫자를 지워나가는 방식으로 해결한다. 먼저 답의 후보는 100 ~ 999 중, 0이 없고, 중복된 숫자가 없는 번호이다. 따라서 숫자에 0이 포함된 경우와 중복된 번호가 있는 경우에 answerList에 1(삭제)을 표시한다. int main(void) { scanf("%d", &N); int answerList[1000 + 5] = { 0 }; for (int n = 100; n 2021. 5. 13.
SWEA 2117 : 홈 방범 서비스 (모의 SW 역량테스트) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 홈 방범 서비스 링크   가능한 큰 K부터 이익이 있는 한, 가장 큰 집의 수를 찾으면 된다.N x N의 MAP을 모두 서비스하기 위한 K는 N + 1이므로, K = N + 1의 영역부터 영역을 줄여나간다.void input(){ scanf("%d %d", &N, &M); for (int r = 1; r  K에 대한 운영 비용 주어진 공식대로 cost 배열에 저장한다.그리고 서비스 영역을 만들기 위해 AREA 배열에 해당하는 영역을 저장한다.row가 1에서 k가 될 때 까지는 column이 양 옆으로 늘어나고, k + 1부터는 줄어들게 만든다.int AREA[22][MAX * MAX][MAX.. 2021. 5. 11.
SWEA 2382 : 미생물 격리 (모의 SW 역량테스트) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 미생물 격리 링크 미생물의 구조체 BIO에는 미생물의 방향, 개수, 그리고 시뮬레이션을 위해 max값을 저장하도록 만든다.아래의 조건을 보자.    ④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.        합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며,       이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.        합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다. 합쳐진 군집이 아닌, 각 군집의 미생물 수가 가장 큰 군집의 방향으로 갱신되므로, max를 저장해서 비교해야 한다. .. 2021. 5. 9.
BOJ 9612 : Maximum Word Frequency 삼성 B형 전체 링크 www.acmicpc.net/problem/9612 해시 테이블을 이용하여 가장 빈도수가 높은 단어와 개수를 세보자. 같은 수의 단어가 있는 경우 사전 순으로 뒤에 있는 단어를 출력한다. 구조체에는 단어의 수와 실제 단어, 그리고 링크드 리스트를 위한 struct pointer가 필요하다. 메모리 풀 방식으로 연결하기 위해 POOL 메모리와 pcnt를 선언한다. typedef unsigned long ul; #define MAX_TABLE (1007) #define MAX_WORD (20 + 5) int N; typedef struct st { int count; char word[MAX_WORD]; struct st *next; }HASHTABLE; HASHTABLE hashTab.. 2021. 5. 9.
BOJ 2745 : 진법 변환 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2745 B진법의 수 N을 10진법으로 변환하는 문제다. 알파벳이 포함되어 있으므로 문자열로 입력을 받는다. 그리고 각 문자에 대해 change 배열에 정수로 저장한다. for (int i = '0'; i 2021. 5. 8.
SWEA 2383 : 점심 식사시간 (모의 SW 역량테스트) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 점심 식사시간 시뮬레이션 문제는 그대로 잘 구현하면 된다. 먼저 좌표를 저장할 RC 구조체를 선언한다.people배열에는 사람의 좌표를, stair 배열에는 계단의 좌표를 저장한다.list는 DFS로 사람을 나눌 때 사용한다.2차원 배열 distance는 계단과 사람 사이의 거리이다. distance[1][3]은 1번 계단과 3번 사람과의 사이를 의미한다.stairLength는 계단을 내려가 이동이 완료되는 시간을 저장한다. (1/2번 계단에 대한 시간)#define MAX (10 + 5)int T, N;int MAP[MAX][MAX];int list[MAX];typedef struct st.. 2021. 5. 7.
반응형

티스토리툴바