공부정리

링크 https://www.acmicpc.net/problem/14503 시뮬레이션 문제이다. 필자는 회전에 대한 구현이 있을 때, 하드코딩을 통헤 dir 변수로 1부터 4까지 if문을 사용하여 해결하지만 이제부터는 반복문을 사용하여 방향을 저장하고 있는 변수를 통해 접근하여 나머지 연산자로 구현을 하려고한다.. [위 : 0] [오른쪽 : 1] [아래 : 2] [왼쪽 : 3] 으로 생각하여 항상 시계방향으로 나타낸다. x,y 값이 있기때문에 방향을 담는 자료를 dx[4], dy[4] 에 위의 인덱스에 이동할 값으로 넣어준다. 왼쪽방향으로 회전하기때문에 +3 %4 으로 처리하면 되고 오른쪽이라면 +1 % 4 180도는 +2 % 4 로 처리하면 방향을 쉽게 처리할 수 있다. 1 2 3 4 5 6 7 8 9 ..

링크 : https://www.acmicpc.net/problem/14499 주사위를 이용한 시뮬레이션 문제이다. 처음에 이것을 굴리면서 무언가 변하는 규칙이 있을것이라 생각했다. 연습장에 6개의 인덱스를 가지는 배열을 통해 열심히 굴리면서 상, 하, 좌, 후 에 따라 변하는 값과 규칙을 찾으려 했지만 쉽지 않았다. 그렇게 고심하다 다행히 스터디원이 힌트를 주면서 쉽게 해결할 수 있었다. 1차원 배열이 아닌 문제의 그림을 적용하여 3*4의 2차원 배열을 이용하여 상하좌우에 따른 규칙을 바로 그려낼 수 있었다. 이것을 만들고 회전했을 때, 밑면의 위치를 그려냈다면 나머지는 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

문제의 출처는 이곳이다. 출처 : https://www.acmicpc.net/problem/3190 필자는 문제를 보고 우선 어떤 자료구조를 사용하여 해결할까? 고민을 조금 하면서, 다음 칸으로 이동할 때, 그 위치를 가지고 있어야한다. 이 후, 이동한 위치에 사과가 없으면 가장 처음에 있던 위치를 제거해야 하기 때문에, 'Queue' 자료구조를 사용하였다. 'Deck'을 사용하거나 다른 방법도 존재한다. 자료구조를 택하였으면, 문제에 있는 조건대로 구현하면 된다. 구현은, 방향을 저장하고 있는 배열만 관리하여 x,y 위치값들을 각 방향에 따라 이동시킨 후, 사과가 없다면 큐의 원소를 제거하는 방식으로 코드를 작성하였다. 아래 코드를 보면 이해할 수 있다. *방향을 선택할때, 필자의 스타일대로 작성하였으..

삼성 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......... 이런식으로 나타낼 수 있다. 이 카메라수와 방향에 따른 조합을 모두 나타내었다면 문제의 내용대로 구현을 하면 된다. 참고로 필자는 이 구현부분을 모두 구현하는 바람에 코드가 길고 깔끔하지 않다. 카메라 종류..