본문 바로가기

삼성 코딩테스트

(5)
[SW Expert Academy] 2115. 벌꿀 채취 C/C++ 풀이 이 문제에 꼬박 하루를 썼다면 당신 믿으시겠습니까? 애매하게 아는 것은 확실하게 아는 것보다 위험하다는 격언을 생각나게 해주는 문제였습니다... :) 문제는 모든 가능성을 이용하는 Brute Force인데, 상자 안의 최대 수익을 구하기 위해 DP(동적 계획법)의 테크닉이 필요하다. 동적 계획법은 예전에 포스팅 했으니 참고하세요. (여기로) 동적계획법(1) 동적계획법이란? 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만 동적계획법의 chavo-s-it-life.tistory.com M개의 영역 안에서 수익의 최댓값을 구하는 것은 반복적으로 사용되기 때문에 cache 배열에 저장해두면 연산을 빠르게..
[SW Expert Academy] 2117. 홈 방범 서비스 C/C++ 풀이 .https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 시뮬레이션 문제. 문제만 처음 봤을 때는 전체 다 순회하려면 시간이 오래 걸릴 것이라고 생각했다. 근데 전체 MAP 크기가 20*20 밖에 안되고 각 포인트에서 다른 포인트까지의 거리(20*20)와 거리마다의 집 수를 기록해놓고 최대 집 개수와 비교했다. 결국 마름모 모양이라는 것은 시작점을 기준으로 (K=2)라면 거리 차이가 1 이하인 점들, (K=4)라면 거리 차이가 3 이하인 점들을 모아놓은 것이라서 한 점을 기준으로 거리마다의 집 수를 구하고 그를 이용해서 수익을 계산해주었다. O(N^5)의 풀이가 나왔지만 최대 N이 20이라서 ..
백준 17144 미세먼지 안녕! C/C++ 풀이 이 문제는 19년도 삼성 SW 역량테스트 기출 문제이다. 산학 장학생으로 시험 풀러갔던 형이 해당 문제를 풀었다고 알려줬는데, 이 문제가 내가 만났던 첫번째 시뮬레이션 문제였다. '그냥 문제에 있는 것을 재현하는게 풀이라니 어떤 다른 알고리즘이 있는게 아니고..??' 하지만 증말 어렵다. 왜 수능형 문제라는지 이해가 감... 아래는 풀이이다. 풀이는 다른건 없고 문제에 나와있는 조건을 똑같이 2차원 배열에 구현했고, 미세먼지를 확산시킬 때 확산된 미세먼지의 값이 다른 연산에 영향을 줄 수 있기 때문에 추가로 2차원 배열을 하나 더 만들었다. #include FILE* in = fopen("input.txt", "r"); int r, c, t; int map[51][51]; int delay[51][51]..
[SW Expert Academy] 5648. 원자 소멸 시뮬레이션 C/C++ 풀이 또뮬레이션 문제 저번 문제를 나름 잘풀었다고 생각했고, 그에 비하면 방향 전환도 없는 개꿀문제라고 생각했다가 큰 코 다친 문제. 우선 이번 문제를 풀면서 느낀 것은 벡터는 정적 배열에 비해서 연산 속도가 엄청나게 느리다. 로직은 거의 똑같이 적은 두 코드를 비교하자면 #include #include #include using namespace std; FILE* in = stdin; //원자의 상태를 저장하는 struct struct mole_info { int x; int y; int dir; int e; }; int t, n; int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { 1, -1, 0, 0 }; // 폭발해서 모인 에너지를 저장해놓음 int delay[4001][40..
백준 14503번 문제 로봇 청소기 C/C++ 풀이 https://www.acmicpc.net/problem/14503 이 역시도 시뮬레이션 문제. 간단히 문제의 상황을 구현만 해주면 된다. 별다른 어려움은 없는 문제! #include //input이 긴 문제는 일일히 input 치기가 귀찮아서 fopen으로 input을 넣는다. FILE* in = fopen("input.txt", "r"); int n, m; int now_x, now_y, now_dir; int map[51][51]; int turn; //문제의 조건에 따라 0 북, 1 동, 2 남, 3 서 int dir_x[4] = { -1, 0, 1, 0 }; int dir_y[4] = { 0, 1, 0, -1 }; int dir_num; // 3 조건인지 4 조건인지 구분 bool possibl..