멍멍멍

SCPC 2016 1차 예선 풀이 목차 SCPC 2016 1차 예선 풀이 문제1. 3N+1 문제2. 징검다리 문제3. 바이러스 문제4. 대피소 문제5. 구두제작 삼성 대학생 프로그래밍 대회(SCPC) 2016 1차 예선에서 제가 푼 방법들입니다. 고수분들의 구현보다 많이 부족하지만 열심히 정리했습니다! 문제1. 3N+1 문제 요약 짝수는 절반으로 나누고 홀수는 3배하고 1을 더하는 규칙을 K번 적용해서 1을 만들 수 있는 수들 중에서 가장 큰 수와 가장 작은 수를 구하는 문제입니다.풀이 아래 그림1처럼 숫자 1에서 시작해서 규칙을 역으로 K번 적용해서 만들 수 있는 수를 모두 구하고 그 중 가장 큰 수와 가장 작은 수를 선택했습니다. 구현 재귀 함수로 위 과정을 구현했습니다. 코드는 주석으로 설명했습니다..

삼각분할 목차 삼각분할 문제 설명 Solution Code 문제 설명 문제 : 백준온라인저지(BOJ) 7737 삼각분할 다각형이 주어졌을 때 삼각형으로 분할 할 수 있는 경우의 수를 구하는 문제다. 5각형은 아래 그림1 처럼 5가지 방법으로 삼각분할 할 수 있다. n각형을 삼각 분할하는 경우의 수를 이라 할 때 을 주어진 값 M으로 나눈 나머지를 출력해야한다. Solution 이 문제는 유명한 카탈란 수 문제이다. 왜 뜬금 없이 카탈란 수가 삼각 분할하는데 나왔을까? 추론 과정을 따라가보자. 아래 그림2 처럼 오각형의 각 변에 2, 3, 4, 5로 숫자를 표시하고 오각형의 대각선으로 추가되는 새로운 변에 나머지 두 변에 적힌 수의 곱을 표시하도록 하자. 여기서부터 직관적으로 n각형을 삼각분할 하는 것이 ..

[구글 Codejam] B번 문제 (2016 Round1 B) 목차 [구글 Codejam] B번 문제 (2016 Round1 B) 문제 요약 생각 흐름 솔루션 코드 정리 이 문제의 이름은 Close Match, 2016 Codejam Round1 B의 B번 문제다. 문제 링크 : https://code.google.com/codejam/contest/11254486/dashboard#s=p1 문제 요약 두 문자열 예를 들어 1?, 2?이 주어진다. ?에 0 ~ 9 사이 숫자를 넣어서 두 수의 차이를 최소로 만드는 값을 출력하면 된다. 이 예시에서는 ?에 각각 9와 0을 넣으면 19와 20을 만들어지고 이 때 두수의 차이가 최소가 된다.주어지는 두 문자열의 길이는 항상 동일하고 두 수의 차이를 최소로 만드..

[Code jam] C번 문제 (2016 Round1 A) 목차 [구글 Codejam] C번 문제 (2016 Round1 A) 문제 요약 입력 예시 생각 흐름 솔루션 코드 이 문제의 이름은 BFFs이고 2016 Round1 A의 C번 문제이다. 문제 링크 : https://code.google.com/codejam/contest/4304486/dashboard#s=p2 문제 요약 어린이집에 N명의 어린이들이 있다. 이 어린이집에서는 원으로 둘러 앉아서 하는 활동을 한다. 이때 어린이 왼쪽 또는 오른쪽에 자기가 생각하는 베스트 프랜드가 앉아있어야한다. 베스트 프렌드는 반드시 한명이다. 불행히도 철수는 영희가 자신의 베스트 프랜드라고 생각하더라도 영희는 철수를 베스트 프랜드라고 생각하지 않을 수 있다. 각 ..

Square Root of Permutation 목차 Square Root of Permutation 문제 설명 Solution Code 문제 설명 문제 : 코드포스 Educational Round 4, E번, Square Root of Permutation길이 n의 순열이란 1부터 n까지의 정수를 한 번씩만 포함하는 배열이다. 예를 들어 q = [4, 5, 1, 2, 3]는 순열이다. 순열의 제곱 p란 순열 q에 대해서 p[i] = q[q[i]]를 의미한다. 예를 들어 q = [4, 5, 1, 2, 3] 일 때 p[1] = q[q[1]] = q[4] = 2 p[2] = q[q[2]] = q[5] = 3 p[3] = q[q[3]] = q[1] = 4 p[4] = q[q[4]] = q[2] = 5 p[5]..

배달 문제 배달 문제 최단거리 bfs dp 문제 요약 링크 : https://www.acmicpc.net/problem/1175 장애물(#)과 지나갈 수 있는 곳(.)으로 구성된 격자판안에 있는 시작점(S)에서 출발해서 두 군데(C)에 배달하는데 걸리는 최소시간을 구하는 문제다. 이때 같은 방향으로 두번 이동 할 수 없다는 조건이 붙는다. 접근 이 문제는 정해진 출발점에서 도착점까지의 최소 거리를 구하는 전형적인 최단거리 문제보다 어려워 보인다. 아래 두 조건 때문이다. 두 군데에 배달해야함 같은 방향으로 두번 이동할 수 없음 같은 방향으로 두번 이동할 수 없다는 조건은 각 지점의 상태를 들어온 방향을 기준으로 오른쪽(0), 오(1), 위(2), 아래(3)로 구체화해서 다음 지점으로 이동할 때 이 방향을..