본문 바로가기

Algorithm

 (640)
[2018 홍익대학교 프로그래밍 경진대회] 16394번 홍익대학교 문제 홍익대학교는 1946년에 개교하였다. 특정 년도가 주어졌을 때, 그 해가 개교 몇 주년인지 출력하라. 단, 홍익대학교는 없어지지 않는다고 가정한다. 문제는 C, C++, JAVA 또는 Python3을 이용하여 해결한다. C 입력 scanf 사용 정수 %d, 실수 %f, 문자열 %s 사용 scanf("%d", &var); 출력 정수 %d, 실수 %f, 문자열 %s 사용 예) printf("%d", var); 필수 라이브러리 stdio.h C++ 입력 cin 사용 예) cin >> var; 출력 cout 사용 예) cout > N; cout
[2019 홍익대학교 프로그래밍 경진대회] 17834번 사자와 토끼 문제 사자와 토끼는 전국적으로 인기를 끌고 있는 재밌는 보드게임이다. 사자와 토끼를 즐기기 위해서는 2명의 플레이어와 1명의 심판이 필요하다. 보드판은 N개의 수풀과 M개의 오솔길로 이루어져 있다. 오솔길은 서로 다른 두 수풀을 양방향으로 연결하며, 어떤 수풀에서 다른 수풀까지 1개 이상의 오솔길을 통하면 반드시 도달 할 수 있다. 게임은 다음과 같은 순서로 이루어진다. 심판이 사자와 토끼의 초기 위치를 각각 어느 수풀로 할지 정한다. 사자와 토끼의 초기 위치는 같을 수 없으며, 사자의 위치는 사자 플레이어에게만, 토끼의 위치는 토끼 플레이어에게만 알려준다. 매 턴마다, 사자와 토끼는 현재 위치한 수풀에서 오솔길 1개를 따라 이동해야 한다. 두 플레이어는 자신의 말을 이동할 위치를 심판에게만 말한다. 이..
[2019 홍익대학교 프로그래밍 경진대회] 17835번 면접보는 승범이네 문제 마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다. 면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다. 모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다...
[2019 홍익대학교 프로그래밍 경진대회] 17830번 이진수씨의 하루 일과 문제 이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은 후 액자에 전시한다. 그러나 그런 진수씨에게도 시련이 찾아왔으니, 종이를 사기 위해 나온 도중에 "오늘의 이진수"를 잊어버리고 만 것이다. 하지만, 진수 씨가 오늘 하루 생각해 놓은 두 이진수에 대해서는 어렴풋이 기억하고 있다. 그 두 이진수를 A와 B라고 하자. 진수 씨가 기억하는 사실은 다음과 같다. A와 B는 N개의 비트로 이루어져 있다. A의 모든 비트는 1이다. 하지만 B의 일부 비트는 기억하지 못한다. 여기서 "오늘의 이진수"를 어느 정도 추측해 볼 수 있다. 예를 들어, N = 4라면 A = 1..
[2019 홍익대학교 프로그래밍 경진대회] 17829번 222-풀링 문제 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 행렬을 2×2 정사각형으로 나눈다. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다. 2번 과정에 의해 행렬의 크기가 줄어들게 된다. 종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지..
[해싱] 백준 10840번 구간 성분 문제 매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다. SA = [a, f, c, d, r, d, e, s, d, c, f, w, s, z, r] SB = [g, e, d, s, r, d, d, e, m, z, r] 신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의 성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다. 즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분 의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에..
[해싱] 백준 2002번 추월 문제 대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다. 소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다. N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대..
문자열 해싱 (String Hashing) map사용 없이 문자열 직접 해싱해서 사용 long long hash(string s){ const int p = 53; const int m = 1e9 + 9; //10^9 + 9 int hash_val = 0; int pow_p = 1; for(int i = 0; i < s.length(); i++){ hash_val = (hash_val + (s[i] - 'a' + 1) * pow_p) % m; pow_p = (p * pow_p) % m; } return hash_val; }

티스토리툴바