알고리즘/백준
-
백준 14499 주사위 굴리기 c++알고리즘/백준 2022. 9. 4. 22:35
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net #include using namespace std; int v[21][21]; int dice[3][2]; //동,서,북,남 int dx[] = {0,0,0,-1,1}; int dy[] = {0,1,-1,0,0}; int n,m,x,y; int turn_dice(int num) { int rem[3][2] = {0,}; int n..
-
백준 2800 괄호 제거 c++알고리즘/백준 2022. 8. 27. 14:06
https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 접근은 간단했다. 괄호쌍을 인덱스 기준 pair로 묶어줘서 1~ 괄호쌍의 개수만큼 백트래킹 하면된다. ** 서로 다른 식 ** 을 제대로 읽지 않아서 20분 넘게 왜 틀렸는지만 보고있었다. 첫 코드때는 백트래킹할때 서로 다른 식 고려를 안한탓에 map 컨테이너에 넣지않고 dfs_combination 함수에서 바로 출력을 했다. 서로 다른식을 고려하려면 map컨..
-
백준 14500 테트로미노 삼성 SW 역량 테스트 기출 문제 c++알고리즘/백준 2022. 7. 6. 16:14
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 이해 후 구상하는데만 20분 구현에는 두시간이 걸렸다. 첫 구상때는 경우의수를 전부 나눠보려고 했는데 그렇게하면 20가지가 넘는 경우의 수가 나오게돼서 하루를 전부 구현해도 안나올 경우의 수였다. 그래서 다시한번 생각을 해보니 ㅗ 모양을 제외한 나머지 케이스는 dfs를 이용했을때 깊이가 3인 것들이었다. 가로 세로의 길이가 최대 500x500 이기에 행렬의 원소 한개씩 브루트포스를 해서 구해..
-
백준 경비원 2564 c++알고리즘/백준 2022. 7. 6. 16:06
https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 경우의수를 나눠서 구현했다. 1. 반대편에 있는경우 1-1) 가로기준 반대 1-2) 세로기준 반대 2. 오른쪽 or 왼쪽에 있는경우 3. 같은곳에 있는 경우 1번 경우가 가장 어려웠는데 이걸 처음부터 하려니까 시간이 오래걸렸다. 가로와 세로의 길이가 다르기 때문에 반대편에 있을때도 가로기준 반대편 세로기준 반대편을 구해줘야했다. 2번의 경우 경우의수가 8가지밖에 안되기때문에 그냥 구현해주는게 더 편할거..
-
백준 15686 삼성 SW 역량 테스트 기출 문제 c++알고리즘/백준 2022. 7. 4. 16:46
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 처음 구상할때 방향성을 어떻게 잡아야할지 생각이 안났다. 입력 수인 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13) 을 살펴보고 백트래킹을 이용한 브루트포스인걸 알아야했는데 알고리즘 분류표를 보고서야 알았다. 생각해보면 2차원 배열 v는 사용할 필요가 없었다. 처음엔 2차원 배열을 이용해 2중 for문으로 경우의수를 하나씩 탐색해 v가 1일때마다 최소값을 찾으려 했는데 그..
-
백준 14889 스타트와 링크 삼성 SW 역량 테스트 기출 c++알고리즘/백준 2022. 7. 1. 16:30
간단한 조합문제다. 조합을 이용해 두개로 팀을 나누고 나눈 팀의 점수합을 비교하면 된다. #include #include using namespace std; int v[21][21]; int min_tmp = 9999; int n; bool check[21]; int c = 0; void combination(int x,int y) { if(y == n/2) { c++; int sum; int sum_lee = 0; int sum_shin = 0; int lee[21]; int lee_cnt = 0; int shin[21]; int shin_cnt = 0; for(int i=1; i
-
백준 14888 삼성 SW 역량 테스트 기출문제 c++알고리즘/백준 2022. 7. 1. 16:29
간단한 백트래킹 문제이다. 숫자가 12개밖에 주어지지 않기 때문에 순열을 이용해 전부 다 확인하면 된다. 처음 코드 짰을때 테스트 케이스를 모두 통과하고 틀린부분이 없다고 생각했는데 다 틀렸길래 next_permutation 함수를 사용하면 틀리게 하는갑다.. 생각해서 dfs를 이용해 순열 코드를 다시 짰다. #include using namespace std; int n; int num[12]; int v[4]; int max_t = -2000000000; int min_t = 2000000000; void dfs(int x,int cnt) { if(cnt == n) { if(max_t x) { min_t = x; } } for(int i=0; i..