본문 바로가기

전체 글137

백준 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.
OAuth 아래 글 내용들을 정리한 것, 원문이 더 자세함 https://hudi.blog/oauth-2.0/ https://gyoogle.dev/blog/web-knowledge/OAuth.html 등장배경 기존에는 A 사이트(ex. 개인 프로젝트 사이트)에서 B 사이트(ex. 구글)의 정보를 조회하려고 하면, B 사이트의 ID/PW를 조회해야 했었다. - ex. 네이버 계정의 이름, 성별, 생년월일로 계정 가입하기 이 방식은 보안에 취약할 수 밖에 없음. A 사이트에서 ID/PW를 해킹 당하면 B 사이트의 계정까지 다 뚫리는 것 .. 그래서 ID/PW를 직접 건네주지 않고도 Open API를 활용해서 B 사이트의 정보를 A 사이트에서 볼 수 있게 하는 것이 OAuth이다. (Open Authorization) .. 2024. 3. 4.
백준 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.
백준 g4 1644 소수의 연속합 c++ https://acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 자연수 N이 주어질 때 연속된 소수들의 합으로 N을 만드는 가짓 수 구하기 풀이 1. 소수 구하기 N N sum -= arr[st] st++ + 주의할 점 N = 1부터 시작하므로 1일 때 주의 전체 코드 /*boj g4 1644 소수의 연속합*/ #include #include #define MAXN 4000005 using namespace std; int N; bool isPrime[MAXN]; vector primes; int main(void) { ios::sync_with_stdio(0); cin.tie(0.. 2024. 3. 2.
백준 s1 2531 회전 초밥 c++ https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 문제 원형의 회전 초밥이 주어진다. k개의 접시를 연속으로 먹는다고 할 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값은? 이때 쿠폰으로 c번 초밥은 먹을 수 있다. 풀이 배열의 어떤 연속적인 상태를 고려할 때, 한 칸씩 +- 가능할 땐 투포인터 사용 가능 st, en : 시작점과 끝점 cnt : 해당 st ~ en에 몇 가지의 초밥을 먹을 수 있는지 ans.. 2024. 3. 2.
백준 s4 2003 수들의 합 2 c++ 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 문제 길이가 N인 수열이 주어질 때, A[i] ~ A[j]의 합이 M인 경우의 수 구하기 풀이 그냥 이중 for문으로 풀면 10^8이라 시간 초과가 날 수도 있음 .. 투 포인터로 O(N)으로 구할 수 있다 수도 코드 // en범위를 넘으면, sum에 더할 수 있는 건 다 더했는데도 M은 못 넘은 거 이므로 끝내는 게 맞음 while: st < N && e.. 2024. 3. 1.

티스토리툴바