![]()
문제 링크 codeforces.com/contest/1471 A. Strange Partition 문제 n개의 정수 배열 a와 정수 x가 주어진다. 원하는 만큼 배열 안에 인접한 원소 두 개를 합쳐 하나로 만들 수 있다. 만약 이 작업을 하면 배열의 원소는 -1씩 줄어든다. 배열의 아름다움이란 배열의 각 원소를 주어진 정수 x로 나눈 후, 올림 한 값들을 더하여 나타내는데, 적당히 작업을 하여, 배열의 아름다움의 최소값과 최댓값을 나타내라. 풀이 1 더보기 나누고 몫을 올림 한다는 것은 원소가 많을 때 이득입니다. 만약 배열 내 원소 k가 있다고 하면, k는 두 가지 경우로 나뉩니다. 1) k가 x로 나누어 떨어지는 경우 : 이 경우 합치나 더하나 차이가 없습니다. 2) k가 x로 나누어 떨어지지 않는 ..
![]()
문제 링크 codeforces.com/contest/1472 A. Cards for Friends 문제 n명의 친구들에게 w x h 크기의 종이를 잘라 나누어 주고자 한다. 자르는 데에는 두 가지 규칙이 있다. w가 짝수일 때, 종이는 반으로 잘라 (w/2) x h 크기 종이 2장으로 만들 수 있다. h가 짝수일 때, 종이는 반으로 잘라 w x (h / 2) 크기 종이 2장으로 만들 수 있다. 주어진 w x h 크기 종이를 적당히 잘라 최소 n 조각을 만들 수 있는가? 풀이1 더보기 w, h 는 반드시 "짝수" 여야 종이의 개수를 늘릴 수 있다. 여기서 종이는 정확히 x 조각을 맞출 필요가 없기 때문에, 최대한 늘이는 방향으로 생각하자. 따라서, 종이의 최대 개수는 w, h 를 각각 "더 이상 짝수가 아..
![]()
www.acmicpc.net/problem/14565 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net 나머지 연산의 덧셈 역과 곱셈 역을 구하는 문제입니다. 덧셈역은 쉽게 구할 수 있지만 곱셈 역은 구하기 어려워보입니다. 1. 덧셈역 구하기 어떤 수 A와 M을 안다고 가정할 때, A%M을 0으로 만드는 덧셈 역 C는 M-A입니다. 이는 생각해보면 매우 간단합니다. 아래의 예를 볼까요? 5 % 13 = 5입니다. 13 % 13 = ..
![]()
문제 링크 문제링크 A. Large Digits 알고리즘 Input을 string으로 받아서 index로 각각에 접근하여 해결할 수 있습니다. 정답 코드 #include using namespace std; int foo(string a, string b) { int A = 0; int B = 0; for (int i = 0; i > ..
![]()
※ 확장 유클리드 알고리즘은 www.crocus.co.kr/1232 블로그의 도움을 많이 받았습니다. 감사합니다. 1. 추첨상 사수 대작전!(Easy) 풀이 www.acmicpc.net/problem/20410 20410번: 추첨상 사수 대작전! (Easy) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 해당 문제에서 M의 범위는 크지 않습니다. 이중 포문을 사용한 브루트 포스를 통해 답을 구할 수 있습니다. #include #include using namespace std; int main() { int m, seed, x1, x2; int a = 0, c = 0, te..
문제 출처 : codeforces.com/contest/1469 A. Regular Bracket Sequence 문제 정확히 하나의 "(", ")" 과 "?"들로 구성된 길이 n의 문자열 s 가 괄호 문자열인지 아닌지를 판단하는 문제입니다. 풀이 1 먼저 괄호문자열이 되지 않는 case 부터 보자면 첫 번째, 문자열 맨 앞에 ")" 가 오거나, 맨 뒤에 "(" 이 오면, 어떠한 위치에 "?"를 배열 하더라도 괄호문자열이 될 수 없습니다. ex) ")??(?)", "??)(" 두 번째, 문자열의 총 길이가 홀수일 경우, 괄호의 짝이 맞지 않으므로 괄호문자열이 될 수 없습니다. 이 두가지를 제외한 나머지 경우는 문자열 s에 "(", ")" 이 한 쌍만 들어간다는 조건이 있기때문에 "?" 문자를 적절히 잘 ..
![]()
* 이 글은 "한국항공대학교 - 알고리즘해석 및 설계" 정렬에 나온 내용을 바탕으로 작성하였습니다. 1. 분할 정복 기법 (Divide - and - Conquer) - 착안점 : 문제의 크기가 커지면 더 풀기가 어렵다. - 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법 - 순환적(recursive)으로 문제를 푸는 하향식(Top - Down) 접근 방법 - 분할 정복의 설계 전략 (1) 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다. (2) 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다. (3) 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을..
안녕하세요! 항공대학교 알고리즘 학회 Koala 에서 이번 겨울방학에 같이 공부하실 분들을 모집합니다! 저희 학회는 프로그래밍 문제 해결 역량을 중요시 하는 현재 기업 채용 추세에 맞춰 알고리즘 스터디를 교외에서 찾을 필요 없이 우리 학교 학생들과 함께 혼자 접근하기 어려운 알고리즘을 다 같이 공부하자는 취지로 만들어졌습니다! 😀저희 학회는 이런 분들에게 추천합니다! ✔알고리즘에 관심이 있으신 분! ✔코딩 꾸준히 해야한다고 생각하는데 혼자하면 안되는 분! ✔삼성, 카카오, 네이버 등 기업 코딩 테스트에 통과하고 싶은데 정보가 없으신 분! ✔acm-icpc, 삼성 scpc 등 알고리즘 대회에 참가하고 싶은데 정보가 없거나 같이 공부할 사람이 없으신 분! 겨울방학 학회 운영 계획 ✅알고리즘 기초 스터디 언어..
이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 안녕하세요. 최근 1. 알고리즘 지식보단 구현 2. 삼성 코딩테스트에 대한 글도 있으면 좋겠다 라는 두가지 의견이 있어서 삼성 코딩테스트에서 자주 사용되는 구현 스킬들에 대해서 적어보려고 합니다. 우선 삼성 코딩테스트에 어떤 유형이 나오는지 잘 모르시는 분들을 위해 간략하게 설명드릴게요. 삼성에서는 몇년동안 아래 두 유형만 출제하고 있어요. 1. 시뮬레이션 2. 완전탐색 그중 시뮬레이션은 문제에 나온 내용을 그대로 구현만 하면 되는 문제로, 특별한 알고리즘 지식 없이 문제에 나온대로 구현만 잘 하면 풀 수 있습니다. 그리고 그 구현도 사실 몇가지 틀 안에서 나오니 몇가지 자주 나오는 구현 형태를 익히면 비교적 쉽게 풀 ..
이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 1학년 - 코딩 문법 이때 익숙해지지 못하면 2학년부터 계속 스노우볼 굴러가니 언어 공부 제대로 합시다. 학점 관리 적당히 3점대 중반이상 해두는게 좋아요. 2학년 - 학점 3점대 중반 이상 관리. 2학년 마친 후 겨울방학에 삼성 상시테스트 A형 취득. 3학년 - 학점관리. 이제 전체 학점 관리도 할 수 있으면 좋지만 그게 힘들고 이미 분야 정했으면 그쪽을 좀더 파고 나머지 학점은 비교적 덜해도 괜찮다고 봐요. 3학년 여름방학, 겨울방학 중 하나는 삼성 상시테스트 A+ 취득에 사용하고 나머지 하나는 인턴이나 프로젝트 경험에 사용. 이 과정으로 졸업하면 학점관리 3점대 중반 이상 되고 상시테스트 A+ 이상 취득에 프로젝트..
이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 코딩테스트에서 나오는 비주류 유형이 몇가지 있는데, 그중 하나인 정수론에 대해 적어보려고 합니다. 코딩테스트에 자주 나오진 않지만, 보통 많이들 가고싶어하시는 상위티어 기업들에서는 나름 빈출이기도 하니 한번쯤 익혀두시면 좋을것 같습니다! 심지어 코딩테스트에 나오는 수준의 정수론은 대부분 쉬워요. 1. 유클리드 호제법 이건 제가 1학년 2학기 c언어 실습 빨리 끝내고 기다리고 있을 때 교수님께서 한번 코딩해보라고 알려주셔서 그 때 처음 알게된 개념이에요. 1학년도 할 수 있는 알고보면 간단한 내용이니 수식 많다고 포기하지 마시고 한번 읽어보세요! 내용은 간단합니다. a와 b의 최대공약수를 gcd(a, b)라고 표현할게요...
이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 문제에 주어진 정보가 많을 경우 구현 시간을 많이 줄일 수 있는 방식이라 코딩테스트, 특히 삼성을 준비하신다면 꼭 알아야 할 방법이라고 생각해서 코딩테스트가 몇개라도 남아있을 때 얼른 올리려고 지금 적습니다. 우선 문제부터 보여드리겠습니다. http://boj.kr/2948 월, 일을 입력받아서 무슨 요일인지 출력하는 문제입니다. 월, 일 순서가 아닌 일, 월 순서로 입력받는다는 함정이 있어요. 이 문제의 해법은 간단한데, 1월 1일이 목요일이니 1월 8, 15, 22, 29일은 모두 목요일입니다. 마찬가지로 1월 2, 9, 16, 23, 30일은 모두 금요일입니다. 그럼 2월 1일은 무슨 요일일까요? 2월 1일은 1월..
