공부정리

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/16234BFS를 통한 4방향탐색을 진행하면서 문제의 조건에 맞게끔 국경선을 열어 인구이동을 진행하여 각 칸의 인구수를 갱신시켜준다. 유의할점은 BFS를 한번진행하고 끝날 때, 인구수를 갱신시켜주면 Time Limit가 발생한다. 처음 모든 칸에 대한 인구이동이 일어난 후 모든칸에 대해 인구수를 갱신시켜야 Time Limit를 피할 수 있다. 이를 위해 한 영역에 대한 나라수와 총합을 저장하는 변수가 필요하다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606..

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/14500 5개 모양의 블럭중 하나를 적절히 놓아 2차원 배열의 칸에 쓰인 수의 최대합을 구하는 문제이다. 이 문제는 회전,대칭에서 5개모양의 블럭이 총 19개의 모양을 가질수 있음을 알고 접근하면 된다. 필자는 이 19개 모양을 모두 탐색하는 방법을 사용하였으며, 한 좌표에서 그 모양이 가능한지를 확인하고 가능하면 최대값들을 갱신시켰다. 그리고 확인한 19개의 모양을 토대로 최대값을 출력하였다. *코드가 깔끔하지 않고 전형적인 탐색방법을 사용해서 구현이 복잡하다, 이것이 최적의 답이 아니고 다른 방법도 존재한다.* 1234567891011121314151617181920212223242526272829303..

삼성 SW역량테스트 문제이다 링크 : https://www.acmicpc.net/problem/14501 이 문제는 DP로도 풀수있고 점화식이 잘 안보인다면 재귀탐색으로 해결할 수 있다. 시간과 값이 있을 때, 가능한 최대값을 구하는 문제이다. 필자는 DP로 푼 답은 이해가 잘 가지않고 점화식도출이 쉽게 되지않아 재귀를 사용하여 해결하였다. N+1일째 결과를 return하는것이 중요하다. 123456789101112131415161718192021222324252627282930313233#include#include#include#include#include#include#include#include#include using namespace std; int n, arrt[16], arrp[16],an..

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/14502 BFS를 통해 2차원 배열에서 영역의 최대값을 구하는 문제이다. 단, 문제조건은 벽을 3개 세웠을때 나타나는 영역의 최대값이다. 그렇다면 3개의 벽을 어떻게 처리할까? 사람은 적당히 이 위치라고 지정할 수 있겠지만 프로그램은 모든 경우를 탐색해야한다. 즉 3중 반복문을 사용해서 벽을 세울 수 있는 곳에 3개의 벽을 설치하고 그때, BFS탐색을 돌려 최대값이 얼마인지 계속 갱신해가며 답을 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960..

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/14888 순열을 사용한 모든 경우를 탐색하면 해결할 수 있다. 자료를 저장해서 어떻게 순열을 해야할지가 중요할 수 있다. 필자는 한배열에 각 연산자를 모두 저장하였으며 0 , 1, 2, 3 을 각각 더하기, 빼기, 곱하기, 나누기로 생각하여 입력에서 받은 모든 갯수를 한 배열에 순서대로 저장하였다. 이 저장값을 기본으로 나올 수 있는 모든 순열에따라 계산을 진행하여 최대값과 최소값을 갱신하여 답을 구하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061..

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/14889 DFS조합 문제이다. 가능한 조합으로 팀을 만들어 만든 두 팀의 차가 최소가 되는 값을 구하는 문제이다. 이때까지 해왔던 DFS조합으로 팀을 선별하여 두 팀의 합을 구하고 차이를 구하면 되지만, 한가지 유의할 점이 있다. N=4 이며 4개의 팀이 있다고 가정하자. visit배열을 통해 방문체크를 하며 조합을 두 팀으로 구성할때, 나올 수 있는 경우는 0 0 1 10 1 0 10 1 1 0 1 0 0 11 0 1 01 1 0 0 여기서 알 수 있는 것은 '0 0 1 1' 경우나 '1 1 0 0' 경우가 같다는 것에 주의해야 한다. 이것에 유의하며 탐색을 진행해야한다. 123456789101112131..

삼성 SW역량테스트 문제이다. 링크 : https://www.acmicpc.net/problem/15683 4가지 방향을 기준으로 재귀 DFS를 통해 구현하는 문제이다. 예를들어 카메라가 하나있을 경우 가능한 4가지 방향에 대해 모두 탐색하면 된다. 그렇다면 카메라가 2개 있을때는 어떻게 처리해야 할까? 1, 2, 3, 4 를 동서남북 방향이라 잡고, A, B라는 카메라고 있다고 하자 표를 간단하게 그린다면 A B 1 1 1 2 1 3 1 4 A B 2 1 2 2 2 3 2 4 etc......... 이런식으로 나타낼 수 있다. 이 카메라수와 방향에 따른 조합을 모두 나타내었다면 문제의 내용대로 구현을 하면 된다. 참고로 필자는 이 구현부분을 모두 구현하는 바람에 코드가 길고 깔끔하지 않다. 카메라 종류..

삼성 SW역량테스트 문제이다. *작년 이문제를 풀어 면접을 봤었다...* 링크 : https://www.acmicpc.net/problem/15686 DFS(조합)를 사용해서 가능한 치킨집을 선별하여 문제에서 요구하는 거리의 합이 가장 작은 결과값을 출력하는 문제이다. 치킨집과 배달할 집의 좌표를 저장하고 선별한 치킨집에 따라 가까운 집을 선별하여 최단거리로 갈 수 있는 조합을 계속 갱신하면 답을 얻을 수 있다. next_permutation() 함수를 사용했지만, 일반 재귀 DFS로도 구현 가능하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616..

삼성 SW역량테스트 기출문제이다. 출처 : https://www.acmicpc.net/problem/16236 이 문제는 BFS+문제의 요구사항에 맞는 구현 능력이 있다면 해결할 수 있다. 처음엔 문제를 읽어도 '뭐 어떻게 하라는 거지' 생각에 문제 이해하는데 시간이 오래 걸렸다. 필자가 언어이해력이 떨어진 것이 문제일 수도 있겠지만 어째뜬, 2번째 테스트케이스를 손으로 그려가며 문제를 이해할 수 있었다. 이 문제는, 상어의 위치, 크기, 먹을 수 있는 물고기 이 3가지를 저장하는 자료구조를 이용하여 BFS탐색을 통해 진행한다. BFS탐색을 하면서 먹을 수 있는 물고기의 위치로 모두 이동하고 그 수가 많다면 문제의 조건에 맞게끔 먼저 먹는다. 그 다음 상어의 위치를 갱신하고 그 위치에서 계속 BFS탐색을..