본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 2143번 : 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 이분탐색으로 푼 문제였습니다. 풀이방법 1. vector a, b에 입력을 받습니다. 2. i ~ j까지의 누적합을 a, b 각각에 저장합니다. 3. 이분탐색을 위해 b를 정렬합니다. 4. a + b = t이므로 모든 a에 대해 b가 t - a인 값을 찾습니다. 해당 값이 여러개 있을 수 있으므로 lower_bound..
(C++) - 백준(BOJ) 7785번 : 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 정렬과 적절한 자료구조를 이용하는 문제였습니다. 풀이방법 1. n만큼 이름, 상태를 입력받습니다. 2. 상태가 "leave"라면 map에 key가 name, value는 0으로 저장합니다. "enter"라면 map에 같은 key를 가지며 value는 1로 저장합니다. 3. vector에 map의 value가 1인 것들의 이름을 저장한뒤 역순으로 정렬합니다. ..
(C++) - 백준(BOJ) 7453번 : 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 이분 탐색으로 해결한 문제였습니다. 풀이방법 1. 입력 받은 후 loop를 돌며 다음을 저장합니다. sums1에는 a[i] + b[j]들, sums2에는 c[i] + d[j]. 이렇게 a + b의 쌍들과 c + d의 쌍들이 저장되었습니다. 이 후 두 배열을 오름차순으로 정렬합니다. 2. 모든 sums1에 대해 sums2로부터 -sums1[i]인 값을 찾아 그 index를 구합니다..
(C++) - 백준(BOJ) 2003번 : 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 누적합 이후 brute force로 답을 찾는 문제였습니다. 풀이방법 연속된 수의 합들이 m이되는 것들의 개수를 구하면 되므로 누적합을 먼저 구해줘야합니다. 1. 1부터 시작해 누적되어 i까지의 합을 구한 값을 sum이라는 배열의 i번째에 저장합니다. 2. sum[j] - sum[i] == m인 개수를 세준 후 출력합니다. Code #include usin..
(C++) - 백준(BOJ) 3425번 : 고스택 https://www.acmicpc.net/problem/3425 3425번: 고스택 각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 www.acmicpc.net 구현 문제였습니다. 풀이방법 * overflow를 고려해야합니다. 계산 결과가 int범위를 초과할 수 있습니다. * divide by zero를 조심하세요. 나눗셈 연산에서 제수가 0인 경우 error입니다. * 문제를 명확히 읽어야 합니다. * 매 명령어 수행시 LIMIT(10억)을 초과할 수 있습니다. * 수행결과에는 stack에 원소가 1개만 있어야합니다. 한 입력마다 입력받은 프로그램을 실행할 때 er..
(C++) - 백준(BOJ) 2580번 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net backtracking문제였습니다. 풀이방법 1. 해당 행의 1 ~ 9사이의 수를 확인했다는 것을 나타내기 위해 2차원 배열들을 사용합니다. rowCk[i][num]은 i행의 num은 이미 확인되었다는 뜻입니다. 같은 방식으로 colCk[j][num]은 j열의 num을 확인했다는 뜻이고 squareCk[(i / 3) * 3 + (j / 3)][num]은 정사각형을 떼어 생각했을 때 몇 번째 칸의 ..
(C++) - 백준(BOJ) 1759번 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 재귀를 통해 적절히 모든 경우의 수를 탐색하면 됩니다. 풀이방법 1. 사전순으로 c개의 알파벳을 l개만큼 순서에 상관 없이 뽑아줍니다. 2. 모음이 최소 1개, 자음이 최소 2개라면 정답이므로 출력해줍니다. Code #include using namespace std; int l,c,ck[16]; char letter[16]; vector candidates; void dfs(int depth, int..
(C++) - 백준(BOJ) 1039번 : 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 이차원 배열 d를 다음과 같이 정의합니다. : d[n][k] => n이라는 수를 만들기 위해 사용한 움직임 개수 k에는 n이 저장됩니다. 2. 재귀함수를 통해 i번째와 j번째를 모두 확인하면서 swap해봅니다. swap의 결과 가장 앞의 수가 '0'이라면 원복해줍니다. 모두 확인한 후에는 원래자리로 다시 swap합니다. 3. 함수의 반환값을 출력합니다. Code #include using namespace std..

티스토리툴바