알고리즘98 백준 g4 20166 문자열 지옥에 빠진 호석 c++ https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 문제 N*M크기의 문자열 배열이 주어진다. 호석은 아무 곳에서나 시작해서 상하좌우+4개의 대각선 방향으로 한 칸씩 움직일 수 있다. 호석이 움직이는 길로 하나의 문자열을 만들 수 있다. 신이 좋아하는 K개의 문자열이 주어진다(K 5) { return; } map[str]++; for (int dir = 0; dir < 8; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; // 범위 밖이면 조절 if (nx < 0) nx += N; if.. 2024. 3. 7. 백준 g5 1351 무한 수열 c++ https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 A0 = 1 Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. 풀이 N=2 이므로 i/2~i까지의 값은 구할 필요가 없다. 필요한 수만 저장할 수 있는 map을 사용해서 해결할 수 있다. ex. P=2, Q=3일 때 A7도 A3까지만 계산하면 됨 map은 값이 지정되지 않은 경우에는 default값으로 0을 넣어서 계산한다. 전체 코드 /*boj g5 1351 무한 수열*/ #include #include using namespace std; long long N; .. 2024. 3. 7. 백준 s3 9375 패션왕 신해빈 c++ https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 T개의 테스트 케이스가 주어진다. N개의 "물건 이름, 물건 종류"가 주어진다. 한 물건 종류에는 하나의 물건 밖에 착용할 수 없을 때, 해빈이가 입을 수 있는 옷 종류의 가짓수는? 풀이 string을 index로 할 수 있는 unordered_map을 사용해서 각 물건의 가짓수를 cnt한다. 한 물.. 2024. 3. 7. 백준 s4 17219 비밀번호 찾기 c++ https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 "사이트 주소 비밀번호"가 N개 주어진다. 이어서 M개의 사이트 주소가 주어지고, 해당하는 사이트 주소의 비밀번호를 출력하면 된다. 사이트 주소 수, 사이트 주소의 길이도 길다(10^5). 그치만 해시(unordered_map) 쓰면 됨 전체 코드 /*boj s4 17219 비밀번호 찾기*/ #include #include #define MAXN 100005 u.. 2024. 3. 5. 백준 s4 1620 나는야 포켓몬 마스터 이다솜 c++ https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 N개의 포켓몬 이름이 주어진다. 그다음 M개의 문제가 주어지는데 이때 포켓몬 이름이 주어지면 -> 그 포켓몬의 번호, 포켓몬의 번호가 주어지면 -> 그 포켓몬의 이름을 맞혀야 한다. N, M 이름은 그냥 배열로 구현하면 된다. 이름 -> 번호는 unordered_map을 사용해서 빠르게 구현할 수 있다. 전체 코드 /*boj s4 1620 나는야 포켓몬 마스터 이.. 2024. 3. 5. 백준 s5 7785 회사에 있는 사람 c++ 이분탐색, 해시 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 N개의 "사람이름 enter/leave"로 구성된 출입기록이 주어진다. enter인 경우엔 출근, leave인 경우엔 퇴근이다. 현재 회사에 남아있는 사람들의 이름을 사전역순으로 출력하기 풀이 이 문제는 이분탐색과 해시(unordered_set)으로 풀 수 있다. 풀이1. 이분탐색 enter의 개수와 leave의 개수를 이분탐색의 upper_bound .. 2024. 3. 5. 백준 g4 13144 List of Unique Numbers c++ https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제 길이가 N인 수열이 주어지고, 이 수열에서 연속 부분 수열을 골랐을 때 겹치는 수가 없는 경우의 수 구하기 풀이 st를 0 ~ N-1까지 이동시키고, 각각의 경우마다 en을 움직일 수 있을 때까지 움직인다. 하나의 st당 경우의 수는 st ~ en의 개수가 되고, (ex. 1 ~ 5 면 1, 12, 123, 1234, 12345 총 5가지를 만들 수 있다) 하나의 st를 수행하고 난 후에는 st++.. 2024. 3. 4. 백준 g5 22862 가장 긴 짝수의 연속한 부분 수열(large) c++ https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 문제 길이가 N인 수열이 주어진다. 최대 K번 원하는 수를 삭제 가능하다. 짝수로 이루어져 있는 연속한 부분 수열 중 최대 길이 구하기 풀이 최대 K번 원하는 수를 삭제 가능 == K번까지 홀수를 봐줄 수 있다. 로 바꾸면 https://kyj0032.tistory.com/71 이 문제와 비슷해진다. 홀수의 개수를 세면서 허용 범위까지 en을 늘려가다가, 홀수의 개수가 K를 넘으면 st++하면서 범위를 줄여나간다. 수도 코드 w.. 2024. 3. 4. 백준 s1 20922 겹치는 건 싫어 c++ https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 길이가 N인 수열이 주어질 때, 같은 원소가 K개 이하인 최장 연속 부분 수열의 길이 구하기 풀이 수도코드 while // en번째를 추가할 차례 cnt[en번째 수]++ if cnt[en번째 수] > K while cnt[en번째 수] > K st++ 하면서 범위 줄이기 length = en-st+1 answer = max(length, answer) en++ 전체 코드 /*boj s.. 2024. 3. 4. 이전 1 2 3 4 5 6 7 ··· 11 다음
