알고리즘
-
[백준 15684번 - 사다리 타기] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 23. 22:26
백준 15684번. 사용한 알고리즘 - 백트래킹 - 구현 어떻게 풀어야 할지는 빠르게 생각이 났었다. h 행 * n 열 짜리 배열을 만든다. 가로행은 몇번째 가로선에 사다리를 놓을지를 나타내고, 세로열은 몇번째 세로선에 사다리를 놓을지 나타낸다. 세로선을 기준으로 오른쪽방향만 저장하려고 한다. 예를들면, 1번 세로선과 2번 세로선 사이에 위에서 2번째 지점에 사다리를 놓는다면 arr[2][1] = 1이 된다. 가지를 치는 기준은 depth 가 3이 될 경우, 또는 depth 가 3이 되기 전, 이미 i번째 세로선이 i번째로 통과되는 경우이다. 애를 먹었던 부분은 1) 9% 에서 시간초과 -> 이는 매번 dfs 를 호출할 때마다 0번째 지점 0번째 사다리부터 검사해서 그런것같길래, dfs 인자로 인덱스를 ..
-
[백준 14891번 - 톱니바퀴] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 23. 15:47
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 톱니바퀴 4개간 서로 마주보고있는 극이 다르면 회전, 다르지 않으면 그대로 둔다. 회전 방향은 마주한 톱니바퀴와는 반대방향이 된다. 처음 상태에서 톱니바퀴간 마주보고있는 극이 서로 다른지를 먼저 검사한다. 그리고 처음 돌리는 톱니바퀴의 번호에 따라 이웃하는 톱니바퀴들의 방향과/ 회전할지말지를 문제 조건에 따라 구현해주면 된다. 결국 구현하면 되는 문제! 완성한 코드 #include #incl..
-
[백준 14889번 - 스타트와 링크] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 20:12
백준 14889번. 총 n 명을 n/2 명씩 두 팀으로 나누고, 각 팀의 능력치 합을 구해서 차이를 최소로 하도록 하는 문제이다. 만약 각 팀에 3명씩 있고, 1,2,3번이 스타트팀, 3,4,5번이 링크팀이라면, 스타트팀 : S12 + S21 + S13 + S31 + S23 + S32 링크팀 : S34 + S43 + S35 + S53 + S45 + S54 가 된다. 사용한 알고리즘 - 백트래킹 순차적으로 탐색하면서 해당 맴버를 선택하거나/선택하지 않거나. 해서 함수를 호출하도록 했다. depth 가 n / 2 이 되면 호출을 멈추도록 재귀를 구현하였다. 그리고 거기서 두 팀 멤버 능력치의 차를 구해서 기존거보다 더 작으면 갱신해주었다. 완성된 코드 #include #include #include #inc..
-
[백준 14503번 - 로봇 청소기] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 18:39
백준 14503번. 사용한 알고리즘 - bfs 방향을 설정하기가 조금 까다로웠던 문제.... 청소한 곳을 체크하기 위한 visited 배열을 두었다. 시작 지점을 큐에 넣고 bfs 시작. 1. 현재 지점의 visited 배열을 true로 2. 현재 방향을 기준으로 왼쪽 부터 차례대로 탐색한다. 나는 아예 배열을 따로 만들어서 현재 청소기가 바라보는 방향인 d에 따라서 탐색할 순서를 설정해줬다. 문제에서 주어진 d 의 순서도 왼쪽방향이면 이렇게 안해도 됐을 텐데.. d의 값은 오른쪽 방향으로 증가하고, 실제 인접한 부분 탐색은 반대 방향으로 해주어야 해서 그냥 배열 하나 더만들어서 편하게 했다. a~ d 까지는 문제에 주어진대로 그대로 알고리즘을 짜면 된다. 처음에는 그냥 청소한부분 map 값을 1로 만들..
-
[백준 14500번 - 테르로미노] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 06:36
백준 14500번. 사용한 알고리즘 - bfs depth 가 4로 정해져있으니 bfs 풀어야겠다는 생각이 들었다. 그리고 테스트 해보니 빠뜨린게 있었는데..! ㅜ/ㅗ/ㅓ/ㅏ 모양은 따로 값을 계산해서 최대값인지를 체크해주어야 한다. bfs 를 위한 visited 배열을 만들었는데, 해당 배열을 dfs 함수의 인자로 넣어주니까 시간초과가 계속 나더라..(call by reference 로 해도..) 그래서 없애고 전역변수로 줬더니 맞았다. 그래도 시간이 빠듯한듯. dfs 풀면 대략 500 * 500 * 4 ^ 4 정도의 시간복잡도가 된다. 완성된 코드 #include #include #include using namespace std; int n, m; vector v; vector visited; int..
-
[백준 14499번 - 주사위 굴리기] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 04:12
백준 14499번. 사용한 알고리즘 - 구현 - 시뮬레이션 문제에 전개도가 그려져 있는 것에 착안하여.. 전개도를 이용하여 풀어보기로 했다. 이렇게 주사위를 a[4], b[4] 배열에 저장해놓는다. 바닥면은 항상 a[1] (= b[1]) , 윗면은 a[3] (= b[3])로 고정하자. 명령이 1 => 오른쪽 2 => 왼쪽 3 => 위쪽 4 => 아래쪽 이다. 오른쪽으로 주사위를 굴리는 경우, 배열 a에 들어있는 숫자들을 왼쪽 방향으로 하나씩 밀어서 재저장한다. 왼쪽으로 주사위를 굴리는 경우, 배열a에 들어있는 숫자들을 오른쪽 방향으로 하나씩 밀어서 재저장한다. 위쪽으로 주사위를 굴리는 경우, 배열 b에 들어있는 숫자들을 아래쪽 방향으로 하나씩 밀어서 재저장한다. 아래쪽으로 주사위를 굴리는 경우, 배열 b..
-
[백준 12100번 - 2048(Easy)] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 18. 22:02
백준 12100번. https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 예전에 많이 했던 게임인데 반갑네.. 그 게임과는 다르게, 블록이 새로 추가되거나 하지는 않고, 주어진 블록들을 가지고 같은 숫자 만나면 합치고 합쳐서 최대 5번까지 이동했을 때 최대 숫자를 출력하는 문제이다. 사용한 알고리즘 - 시뮬레이션 - dfs - 구현 음.. 또 다 해봐야지.. 라는 생각밖에 안들었다. 백트래킹으로 promising 하지 않..
-
[백준 14501번 - 퇴사] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 18. 15:13
백준 14501번. 사용한 알고리즘 - dfs N이 최대 15이기 때문에, dfs 재귀로 시도를 먼저 해보았다. i번째 날부터 시작한다고 가정했을 때 dfs 를 호출한다. (총 N번 호출) 각 경우마다, 해당 날에 상담을 하고, 다음 상담 가능일부터~ N일 까지 dfs 를 호출한다. (N - 현재 날 - Ti 번 호출) 현재 날짜에 해당 상담을 하면 N일이 넘어가거나, N일이면 반환. 완성 코드 #include #include #include using namespace std; int n; vector v; int ans = 0; void dfs(int time, int curr_t, int result) { if (time + curr_t > n) { ans = (result > ans) ? resu..