알고리즘/SW 역량 테스트 (39) 썸네일형 리스트형 [백준] 17837. 새로운 게임2 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 2019 하반기 삼성 공채 SW 역량테스트 시뮬레이션 문제 입니다. 제가 봤던 시험 시간에 나온 두 문제중 하나 였는데 게리멘더.. 4008. [모의 SW 역량테스트] 숫자 만들기 백준 14888. 연산자 끼워넣기와 똑같은 문제입니다. 저는 연산자 끼워넣기 문제를 순열을 이용하여서 연산자들을 줄세워서 나올 수 있는 모든 경우의 수를 확인했습니다. 그리고 그 때마다 숫자 계산을 하여 최댓값과 최솟값을 구했는데, 이번문제도 처음엔 그렇게 풀려고 시도해봤는데 시간초과가 발생했습니다. 극단적인 예로 '+' 연산자가 10개가 있으면 실제로는 한 번만 계산하면 되지만, 10!의 순열을 계산하면서 거기에서 시간초과가 발생한 것 같습니다. 중복된 연산자를 처리하기에 순열을 이용하면 비효율적입니다. 그래서 이번 문제는 재귀를 통한 완전탐색으로 해결했는데, 코드를 보면 쉽게 이해할 수 있기 때문에 문제풀이 순서는 생략하려고 합니다. 이러한 패턴의 문제들이 많은것 같은데 풀이 방법을 숙지해야겠고, 백.. [백준] 14500. 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 입력받은 2차원 배열에서 처음 부터 끝까지 완전탐색하면서 주어진 정사각형 4개를 이어 붙인 테트로미노 영역의 값을 계산해서 최대값을.. [백준] 14890. 경사로 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제를 조금 더 쉽게 풀기 위해서 다른 블로그를 통해서 아이디어를 얻을 수 있었습니다. 처음에 저는 내려가는 경사로가 아닌 올라가는 경사로만 만들면서 행과 열별로 탐색하려고 생각했는데, 그렇게 하면 반대방향에서도 고려해야 하므로 코드가 길어지고 복잡했습니다. 이 점을 해결하기 위해서 1. 올라가는 경사로만 행과 열별로 판단 하는 것이 아닌, 내려가는 경사로도 놓을 수 있다고 가정합니다. 먼저 올라가는 경사로를 놓을 .. [백준] 17143. 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 이 문제에서는 어떻게 시간초과 나오지 않게 하는지 생각을 해야합니다. 저는 그래서 먼저 상어들의 정보를 가지고 있는 Shark 라는 C.. 2382. [모의 SW 역량테스트] 미생물 격리 시뮬레이션 문제입니다. 제가 문제를 풀면서 막혔던 부분은 두 개 이상의 군집이 한 셀에 모이는 경우에 군집들이 합쳐지게 되는데, 이동 방향을 군집들 중 미생물 수가 가장 많은 군집을 따라가야 한다는 것이었습니다. 저는 처음 생각했을 때 미생물들을 한 칸씩 움직이면서 겹치면 더 많은 미생물 수를 가진 군집의 이동방향으로 그 때 마다 바꿨습니다. 하지만 이렇게 되면 생기는 문제가 한셀에 미생물 수가 각각 30 -> 50 -> 70 를 가지고 있는 군집들이 순서대로 겹친다고 가정하면 처음에 30과 50을 더해서 미생물 수가 80이고, 50인 방향을 따라가는데 세 번째에서 70 을 가지고 있는 군집이 겹치게 되면 앞에서 더해진 미생물 수 80을 가지고 있고, 70이 더 작기 때문에 150으로 합쳐지면서 방향은 .. 2105. [모의 SW 역량테스트] 디저트 카페 2차원 배열에서 4개의 점을 정하고 그 점에 있는 값들을 확인 하는 문제입니다. 이 문제에서 핵심은 4개의 점을 정하는 것인데 제가 예전에 정리한 적이 있었던 삼성 기출 문제인 게리멘더링2 ( https://daily-life-of-bsh.tistory.com/130 ) 를 참고하시면 될 것 같습니다. 4개의 점을 정하고 문제를 풀면서 제가 실수했던 부분은 한번의 for문으로 1번점에서 2번점까지 왼쪽 대각선 아래로 가면서 값을 확인하는 동시에 4번 점에서 3번 점으로 오른쪽 위로 올라가면서 값을 확인하려고 했습니다. 하지만 이렇게 하게 되면 1번 -> 2번으로 가는 길과 4번 -> 3번으로 가는 길에 동시에 같은값이 있으면 그것을 잡아내지 못했습니다. 그래서 각각의 방향을 가는 독립적인 for 문 4번.. [17779] 게리맨더링 2 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 2019 삼성 하반기 공채 코딩테스트 문제입니다. 저도 실제로 시험장에 가서 풀었던 두 문제중 한개였는데, 이 문제에 3시간을 .. 이전 1 2 3 4 5 다음
