'study/coding test' 카테고리의 글 목록 (2 Page)

study/coding test

37건

백준 3108 - 로고

1. 문제 정리 - 한붓그리기(해밀턴 경로)문제이다. - 명령어는 무시를 해도 좋다. - 거북이의 첫 좌표는 0,0 이며, 연필을 내려놓은 채로 시작한다. - 겹치는 직사각형을 하나로 간주하여, 해당 직사각형의 수의 최소값을 정답으로 한다. 2. 접근 - 처음에는 bfs로 접근하여으나 직사각형이 겹치는 조건을 이용하여 문제를 해결하기로 하였다. - 직사각형이 서로 겹치지 않는 조건은, 서로 떨어져 있을 때(즉, 한 직사각형의 가장 큰 x좌표가 다른 직사각형의 가장 작은 x좌표 보다 작을 때 등)와 내포하고 있을 때(큰 직사각형이 작은 직사각형을 품고 있을 때)로 총 각 6가지가 된다. - 위 6가지 경우를 제외하고는 직사각형은 서로 겹치므로 겹친 직사각형에 하나의 번호를 배정해 하나의 연합으로 간주한다...

백준 2251 - 물통

1. 문제 정리 - 부피가 A, B, C인 세개의 물통이 있다. - 초기값은 부피가 A, B인 물통은 0, C인 물통은 가득차 있다고 가정한다. - 물통은 한 물통이 완전히 비거나, 다른 물통이 완전히 찰 때까지 부을 수 있으며, 물의 손실은 없다. - 첫번째 물통(부피가 A인 물통)에 채워져 있는 물이 0일 때, 가능한 모든 마지막 물통(부피가 C인 물통)에 있을 수 있는 물의 양을 출력한다. 2. 접근 - BFS로 접근하였다. - A->B, A->C, B->A, B->C, C->A, C->B 총 6개의 물통에서 물을 옮길 수 있는 경우의 수가 있다. - 6개의 경우를 이동경로로 생각하여 BFS 순회를 통해 가능한 경우의 수 중, A부피의 물통에 물이 없을 때 C 부피의 물통에 있는 물을 출력한다. 3..

백준 1525 - 퍼즐

1. 문제 정리 - 3*3 표가 주어진다. - 각 칸에는 0에서 8까지의 수로 채워져 있다. - 0의 위치를 옮겨 왼쪽 위부터 1 2 3 4 5 6 7 8 0 으로 채워넣는 최소 이동 횟수를 출력한다. 배치를 만들 수 없다면 -1을 출력한다. 2. 접근 - 0의 위치를 중심으로 bfs를 진행하고자 생각했다. - 하지만 중복 배치를 방지하기 위한 visited 부분에서 배열을 사용하기 보다 string 을 저장할 set Container를 사용하고자 했다. - 그를 위해 수의 배치를 문자열로 저장하도록 접근하였다. 3. 풀이 #include #include #include using namespace std; string ans = "123456780"; struct check{ string s; int ..

백준 1451 - 직사각형으로 나누기

1. 문제 정리 - n * m의 직사각형이 주어지며, 각 칸에는 한자리 정수가 주어진다. - 입력받은 직사각형을 3개의 직사각형으로 나눈다. - 각 나누어진 직사각형에 속해있는 정수의 합을 구하고, 그 합의 곱의 최대값을 출력한다. 2. 접근 - 처음에는 어떻게 접근해야할까를 한참 고민했다. - 직사각형이 나누어질 수 있는 케이스를 나누어 완전탐색을 시행했다. 3. 풀이 #include using namespace std; int n, m; int a[50][50]; long long ans = 0; long long sum(int sx, int sy, int ex, int ey){ long long ret = 0; for(int i = sx; i ans) ans = temp; } } // case 3 ..

백준 11451 - 팩맨

1. 문제 정리 - 팩맨 두개가 존재한다. - 팩맨은 동서남북 4개의 방향으로 움직일 수 있다. - 하나의 팩맨을 움직이면 다른 팩맨 또한 같은 방향으로 움직인다. - 벽('X')이 존재하는 칸으로 가려하면 해당 팩맨은 움직이지 않는다. - 유령('G')이 존재하는 칸으로는 이동할 수 없다. - 팩맨이 화면 밖으로 나가면 반대에서 나타난다. - 두개의 팩맨의 좌표를 갖게 할 수 있을 때, 해당 지점까지 이동 방향의 문자열과 이동 횟수를 출력한다. 2. 접근 - BFS로 풀 수 있는 문제라 생각하였다. - 하나의 팩맨을 기준으로 움직일 때 다른 팩맨의 움직임도 계산을 해주었다. - 방문 기록을 위한 4차원 배열을 만들었다. 3. 풀이 //2021.12.21 #include #include #include ..

백준 1744 - 수 묶기

1. 문제 정리 - N개의 수열이 주어진다. - 수열의 순서는 바꿀 수 있으며 수열의 각 값은 서로 다른 수와 순서쌍으로 묶을 수 있다.(여기서 말하는 서로 다른 수는 인덱스가 다른 수로, 값은 같을 수 있다. 즉 자기 자신이 안 된다.) - 순서쌍으로 묶은 수는 서로 곱하여 하나의 수로 인식한다. - 모든 값의 합이 가장 크도록 한다. 2. 접근 - 그리디 알고리즘으로 해결해야겠다고 생각하였다. - 가장 큰 수 두개의 곱이 가장 클 것이므로 내림차순으로 정렬한 뒤 문제를 풀고자 하였다. - 음수 간의 경우 가장 작은 수 두개의 곱이 가장 클 것이므로 음수의 경우는 오름차순으로 정렬해야 했다. - 양수가 내림차순, 음수가 오름차순인 이유는 벡터의 뒤에서부터 계산해나가기 위함이다. - 0은 어디에 들어가도..

백준 11399 - ATM

1. 문제 정리 - N명의 사람과 각 사람의 인출하는데 걸리는 시간 Pi가 주어진다. - 한번에 한명만 인출이 가능하며, 그 외의 사람은 기다려야 한다. - 각 사람들의 (기다리는 시간+인출하는 시간)의 합이 최소가 되도록 한다. 2. 접근 - 그리디 알고리즘으로 풀 수 있다. - 뒷 사람의 기다리는 시간을 짧게 한다 = 그 앞의 사람의 인출 시간을 짧게 한다. 로 볼 수 있다. - 즉, 인출 시간이 가장 빠른 사람을 앞으로, 가장 느린 사람을 뒤로, 즉 오름차순으로 정렬하여 순서대로 인출시킨다. - 앞에서 풀었던, (백준 1931 - 희의실 배정) 문제와 유사하다. 3. 풀이 #include #include #include using namespace std; int n; vector p; int ma..

백준 1931 - 회의실 배정

1. 문제 정리 - N개의 회의에 대해 회의실을 배정한다. - 각 회의는 시작 시간과 끝나는 시간이 주어진다. - 각 회의는 겹쳐서는 안 된다. - 회의는 끝나는 동시에 다음 회의가 시작될 수 있다. - 배정 가능한 회의의 최대 개수를 출력한다. 2. 접근 - 회의의 시작 시간, 종료 시간, 소요 시간 중 어떤 것을 기준으로 우선할 것인지 정해야 한다. - 시작 시간을 기준으로 할 시, 예제를 기준으로 0-6 -> 6-10 -> 12-14(3개)의 반례가 생긴다. - 소요 시간을 기준으로 할 시, 예제를 기준으로 3-5 -> 5-7 -> 8-11 -> 12-14(4개)로 일견 해결법으로 보이나, 가령 회의가 0-7 , 4-5, 7-12 세개가 주어졌을 때, 결과값 4-5 (1개)로 반례가 생긴다. - 종..

백준 1783 - 병든 나이트

1. 문제 정리 - 나이트는 N*M의 체스판 위에 존재한다. - 나이트는 총 내게의 방법으로 이동할 수 있다.(상2-우1, 상1-우2, 하2-우1, 하2-우1) - 이동 횟수가 4번 이상일 경우 이동 방법을 모두 한번씩 사용해야한다. 2. 접근 - 나이트의 이동 가능 방법에 따라 케이스를 나누어 접근한다. - 높이가 1일 때 : 나이트는 움직일 수 없다.(위 아래 방향이 항상 포함되어 있기 때문에) - 높이가 2일 때 : 나이트는 상1-우2, 하1-우2 방향으로 움직일 수 있다. 이렇게 움직일 때, 방문 칸수는 (M+1)/2인데, 이 값이 4보다 커질 경우 마지막 조건을 위반하므로 이 때는 4를 출력한다. - 가로가 6 이하일 때 : 상2-우1, 하2-우1 방향으로 움직여 방문 칸수는 m이나, 이 값이 ..

1 2 3 4 5

티스토리툴바