공부정리

문제 출처 : https://www.acmicpc.net/problem/17779 삼성 역량테스트 2019년 하반기 기출문제이다. 푸는 방법은 여러가지가 있으며 대부분 그냥 for문을 사용하여 문제에 맞게 구현하였다. 범위에서 실수하지 말고 4중 for문으로 모든 경우에 문제에서 주어진 '구간 5' 부분을 채우고 나머지 부분을 채우는 구현문제이다. 필자는 '구간 5'부분을 채운다음 나머지 부분을 BFS탐색으로 채워 넣었는데 여기서 기본적인 for문의 구현방식보다 실행시간이 오래 걸렸다. 그리고 이 문제에서는 '구간 5'를 시작하는데 해당 모양이 이루어질 수 없는 상태라면 배제해도 된다. 그러니까 시작할 위치 (r,c)에 대해 d1,d2 값을 빼거나 더했을때, 범위를 벗어나는 경우는 무시하면 된다. 구현을..

문제 출처 : https://www.acmicpc.net/problem/17822 2019 하반기 문제라고 해서 한번 풀어보았다. 이 문제는 시키는 대로 잘 구현해서 풀었다. 다른사람은 이런 시뮬레이션에 BFS를 함께 사용하여 푸는 경우도 봤지만, 필자는 그저 시키는대로 하나하나 확인하며 해결하였다. 문제는 이 문제에서 회전 후, 바뀌는게 없으면 전체 수의 평균값을 가지고 +1 혹은 -1 을 하는 경우에서 평균과 같은 값이면 그대로 두어야 하는것을 잘못하여 하루종일 걸렸다... 이걸 찾는대도 오래걸렸다... 문제에서 크다와 작다로 표기되어 있는데.. 암튼 같은 경우에는 그대로 두면 된다. 그리고 가로, 즉 한 원에 들어있는 수가 m개라는걸... 다 풀고 보았다. 4개로만 되어있길래 4개를 기준으로 풀었었..

이 문제의 출처는 아래와 같다. 참고로 '연구소2'와 매우 비슷하다. https://www.acmicpc.net/problem/17142 https://www.acmicpc.net/problem/17141 먼저 이문제를 푸는데 필요한 것은 '조합' 을 먼저 작성하고 'BFS 탐색' 을 실시하여 탐색시 문제의 조건에 맞게 구현하면 해결할 수 있다. 먼저 입력을 받고 '조합'을 생각하자. 이 문제에서는 바이러스의 전체갯수 중에서 몇개를 선택하기 때문에, 바이러스의 위치를 저장한 vector를 DFS를 통해 조합을 구현하였다. DFS 함수에서 골라야 하는 갯수를 모두 선택하였으면 그 떄, BFS를 시작하면된다. 처음 시작할때, 시작하는 바이러스를 모두 큐에 넣어주고 -1로 초기화된 방문여부 확인값을 0으로 만..

문제 출처 : https://www.acmicpc.net/problem/17140 위 문제는 '삼성 역량 테스트' 기출문제로 분류되어 있다. 먼저 다른 사람의 코드는 보지 못했다. 필자는 문제를 읽으면서 그냥 하라는 대로 구현하는 문제로 생각하고 시키는대로 풀었다. 언제나 그렇듯 설계를 잘하고 코드를 짜면서 제대로 돌아가고 있는지 확인하는 과정이 필요하다. 이번에도 확인하면서 잘 돌아가는것을 보았으나 한두개의 일부분만을 확인했지 10번 20번 돌아가는 경우의 검증을 제대로 하지 않아서 오류를 찾는데 시간이 좀 걸렸다. 이제 문제를 풀어보자. 3x3 matrix를 기준으로 R연산 혹은 C연산을 하는 문제이다. 연산을 구현하기 위해서는 각 Row, Collum 마다의 값과 횟수를 기준으로 정렬하는 방법이 필..

이 문제의 출처는 아래와 같다. https://www.acmicpc.net/problem/17135 '삼성 A형 기출문제' 문제집에 있는 문제이다. 우선 필자는 단순히 구현했다. N,M 의 범위가 작기 때문에 모든 경우를 for 반복문으로 돌려 문제에서 주어진 조건에 맞게 구현하였다. 3명의 궁수를 3중 for문으로 모든 경우에 위치시키고 각 궁수마다 적의 (x좌표, y좌표, 궁수와의 거리) 가지도록 하는 구조체를 사용해 2차원 map에서 적을 만나는 경우 각 궁수별로 해당 적까지의 거리와 위치를 vector에 저장하였다. 해당 벡터들의 크기가 1보다 크다는 뜻은 여러 적을 죽일 수 있으다는 뜻이고 문제의 조건에 맞게 거리가 가장 가깝고 제일 왼쪽에 있는 적을 제거하도록 벡터를 정렬하여 적을 줄여나갔다...

본 문제의 출처는 아래에서 확인할 수 있다. https://www.acmicpc.net/problem/17070 이 문제는 인증된 문제집의 '삼성 A형'에서 확인할 수 있다. N의 크기가 매우작으며 오른쪽과 아래로 밖에 이동하지 않는다. 연결할 수 있는 모든 경우를 탐색하도록 한다. 필자는 BFS를 사용하였다. 방향 즉, 파이프 연결에 따른 이동 방법에 따라 파이프를 모두 연결하여 탐색을 진행하는데 여기서는 중복된 모든 경우를 봐야하기 때문에 방문체크여부를 할 필요가 없다. 큐에 연결가능한 경우를 모두 넣어 조건에 맞게 진행하면 쉽게 해결할 수 있다. 방향에 따른 처리 간소화하여 코드를 작성할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

본 문제는 아래의 출처에서 확인할 수 있다. https://www.acmicpc.net/problem/17471 인증된 문제집에서 '삼성 A형 기출'에 있는 문제이다. DFS를 활용하여 문제를 해결할 수 있다. 필자는 2그룹으로 나누는 방법으로 부분집합을 사용하였으며, 그룹을 나눈 후, 문제의 조건에 맞게 DFS를 수행하였다. 다른사람은 조합, Union-find 등을 사용하였으며, 필자는 부분 집합으로 그룹으로 나누었다. N의 크기가 작기 때문에 부분집합으로 중복된 그룹을 또 탐색하지만, 시간초과에 걸릴 것 같지는 않았다. 부분집합으로 하게되면 (1,2,3) (4,5,6) 이란 그룹을 (4,5,6) (1,2,3) 으로 또 탐색을 하게된다. 그룹화 이후, DFS를 통해 각 그룹에 맞게 탐색이 가능한지 확..

링크 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 위치값들을 각 방향에 따라 이동시킨 후, 사과가 없다면 큐의 원소를 제거하는 방식으로 코드를 작성하였다. 아래 코드를 보면 이해할 수 있다. *방향을 선택할때, 필자의 스타일대로 작성하였으..