컴굥일지

문제 https://www.acmicpc.net/problem/13414 문제 내용 어떤 수업의 수강신청 학번 목록을 받는다. 여러 번 클릭한 학생은 자신이 얻은 순서의 가장 마지막 순서를 가지게 된다. k명 수강 가능하다고 할 때, 해당 수업을 들을 수 있는 학생의 학번을 출력하면 된다. 문제 풀이 unordered_map으로 (학번, 대기순서)를 저장했다. 이후 해당 내역을 {대기 순서, 학번}의 형식으로 vector에 저장한 뒤, 정렬을 진행했다. k명 이내에 드는 학생들만 출력하면 된다. 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cou..

문제 https://www.acmicpc.net/problem/17219 문제 내용 사이트 주소와 비밀번호를 저장해 둔 뒤, 사이트 주소가 주어졌을 때 비밀번호를 출력하면 된다. 문제 풀이 unordered_map을 통해 쉽게 문제를 해결할 수 있다. 굳이 정렬이 필요 없기 때문에 map이어야 할 필요가 없다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; unordered_map site_name; string site, name; while (n--) { cin >> site >> name; site_name..

문제 https://www.acmicpc.net/problem/21921 문제 내용 블로그를 시작한 후 N일이 지났다. X일 동안 가장 많이 들어온 방문자 수를 출력한다. (0명이면 SAD 출력) 최대 방문자 수가 0명이 아니라면 둘째 줄에 기간이 몇 개 있는도 출력한다. 문제 풀이 슬라이딩 윈도우로 문제를 해결할 수 있다. 나는 연속된 X일의 모든 방문자 수를 벡터에 저장한 후, max_element와 count 함수를 통해 해결했다. 코드 #include #include #include using namespace std; int main() { int n, x; cin >> n >> x; vector arr(n, 0); for (int i = 0; i > arr[i]; v..

2023-1학기의 마감으로 드디어 대학생활 8학기가 끝났다. 학생의 신분이 끝난다는 게 무섭기도 하고 아쉽기도 하고... 일단 바로 백수가 되기는 싫어서 졸업 유예를 신청했다. ㅎㅎ (뭐.. 준백수인 건 똑같지만, 그래도 졸업유예는 아직 학생이라고 스스로 세뇌를 걸고 있다.) 6월 30일까지였던 인턴 생활 이후, 7월에는 약간 심란했다. 매일 아침 일어나서 출근을 하던 게 없어지니까 좋긴 한데 허전했다. 늦게 일어나도 된다는 점은 좋았다. 근데 인턴 기간 동안에는 그냥 생각 없이 주어지는 업무만 생각하면 되었어서 좋았는데, 이제는 그게 안 된다는 점이 참.... 아쉬웠다. 그리고 이제 취준을 시작해야 하는데, 쌓아둔 게 아무것도 없는 것 같아서 더 그런 것 같다. 프런트엔드 개발자로 취준 하려는데 rea..

문제 https://www.acmicpc.net/problem/1759 문제 내용 입력받은 알파벳 C개로 암호(길이 L)를 구성하면 된다. (주어지는 입력은 모두 소문자이며 중복은 없다.) 이때 만든 암호는, 알파벳이 증가하는 순서여야 하며, 모음이 최소 1개, 자음도 최소 2개를 포함해야 한다. (중복 X) 위 조건에 맞는 암호를 사전식으로 출력하면 된다. 문제 풀이 백트래킹으로 문제를 해결하면 된다. 기본적인 백트래킹 코드를 통해, 중복 없고 알파벳이 증가하는 순서로 암호를 만드는 것이 가능하다. 단, 모음 1개 이상, 자음 2개 이상 포함했는지는 출력 직전에 검사하도록 했다. 코드 #include #include #include using namespace std; int L, C; char arr..

문제 https://www.acmicpc.net/problem/21608 문제 내용 N*N명의 학생이 N*N 크기의 격자에 아래 방법대로 앉는다. (격자는 (1,1)부터 (N,N)까지이다.) 각 학생별로 그 학생이 좋아하는 학생들 4명이 입력으로 주어진다. |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/138476 문제 내용 한 상자에 담으려 하는 귤의 개수 k와, 귤의 크기를 담은 배열 tangerine을 입력받는다. 귤의 개수 k개를 채우되, 귤의 크기의 종류가 최소가 되게 하는 크기의 개수를 구하면 된다. 문제 풀이 k개를 채울 때 귤 크기의 종류를 최소화시켜야 할 뿐, 특정 크기의 귤을 모두 사용해서 k개를 채우는 문제가 아니다. 이 부분을 잘못 생각해서 한참을 고민해야 했다. k개를 채울 때 귤 크기의 종류를 최소화시키려면, 귤이 가장 많은 크기부터 사용하면 된다. 그럼 각 크기별로 귤이 몇 개인지를 구해야 한다. 나는 위 내용을 이분 탐색을 사용하여 풀었다. upper_bound와 l..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12914 문제 내용 한 번에 갈 수 있는 칸은 1칸 또는 2칸이다. n번째 칸까지 가려고 할 때, 도달하는 방법이 몇 개인지 구하면 된다. (단, 1234567로 나눈 나머지를 구할 것) 문제 풀이 문제를 보자마자 dp를 떠올렸다. 문제를 풀기 위해 n=5일 때까지의 가짓수를 모두 적어보았다. 위의 사진과 같이, n-1칸까지 뛰고, +1칸 가는 것 경우와 n-2칸까지 뛰고, +2칸 가는 경우로 나눌 수 있다. 코드 #include #include using namespace std; int solution(int n) { int dp[n+1]; dp[1]=1; dp[2]=2; for(int i=..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12953 문제 내용 입력받은 수들의 최소공배수를 구하면 된다. 문제 풀이 기본적으로 최대공약수/최소공배수 구하는 식을 알면 된다. 보통은 2개의 수에 대해서만 최소공배수를 구하지만, 이 문제에서는 최소 공배수 구하는 것을 N-1번 반복하면 된다. 코드 #include #include using namespace std; int calcGCD(int a, int b) { // 반드시 a가 더 크게 입력할 것 while (b) { a %= b; swap(a, b); } return a; } int calcLCM(int a, int b) { if (a < b) swap(a, b); return a /..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12980 문제 내용 문제에 나와있는 대로, 0번 위치에서 N번 위치까지 이동해야 한다. 이때 현재 있는 위치*2 인 곳으로 갈 때에는 건전지가 소모되지 않지만, 현재 있는 위치+k 인 곳으로 갈 때에는 k만큼의 건전지가 소모된다. 건전지 소모를 최소한으로 하여 N번 위치까지 이동하고자 할 때, 건전지 사용량을 출력하면 된다. 문제 풀이 문제를 이해해 보기 위해 0~19까지 건전지 소모량을 적어보았다. 빨간색은 이전 위치에서 X2 한 경우이고, 파란색은 +1을 한 경우이다. 잘 살펴보면, 짝수 인덱스는 모두 X2를 통해 도달할 수 있고, 홀수 인덱스는 바로 앞 인덱스에서 +1을 하면 도달할 수 있..