SY DevLog

난이도는 어렵지 않은 문제이다. 어떤 수 N으로 나눌 때 나머지는 항상 N보다 작다. "나머지 = 몫"인 경우를 구하면 되므로 N보다 작은 수 i에 대하여 "i = 나머지 = 몫"이라고 할 때, "몫*N + 나머지"가 문제에서 구해야 하는 자연수이므로 i*N + i (단, i

https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 재귀함수를 이용하여 문제를 풀었다. 게임판을 (0,0)부터 시작하는 좌표상에 위치시킨다고 할 때, L자 블록이 특정 위치 (tx,ty)를 포함하는 경우는 다음과 같이 총 12가지이다. (tx,ty)를 기준으로 했을 때 (tx,ty)를 포함시키는 L블럭이 감싸는 3개의 좌표 모두 흰 칸이어야만 L블럭을 사용할 수 있다. 즉, (tx,ty) (x1,y1)..

https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제 자체는 정말 쉬운 편에 속한다. 어떤 문자열이 주어졌을 때, 팰린드롬인지 아닌지 판별하는 문제인데 게다가 심지어 문제에서 재귀 함수까지 직접 짜서 준다. 재귀함수 호출 횟수도 출력해야 하기 때문에, 주어진 재귀함수에다가 카운트 변수 하나 추가하여서 호출 될 때마다 +1 해주면 끝이다. ...라고 생각했으나, 계속 5% 대에서 실패 다음 코드는 실패가 떴을 때의 제출한 코드이다. #include #include int T; int cnt; int..

https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 알고리즘 학생들을 짝지어 주되, 짝이 된 학생끼리는 서로 친구이도록 짝을 지어줘야하는 문제이다. 친구인지 아닌지 여부는 미리 주어진다. 학생의 수가 총 4명이고 n = 4, 친구쌍이 총 6쌍이고 다음과 같을 때 m = 6 (0,1) (1,2) (2,3) (3,0) (0,2) (1,3)가 서로 친구인 쌍이다. 4 6 0 1 1 2 2 3 3 0 0 2 1 3 0번 학생부터 4번..

어떤 문자열(T)에서 특정 문자열(P)를 찾을 때 사용하는 알고리즘 예를 들어, 문자열(T) : "CDABABKABADABABC" 문자열(P) : "ABABC" 문자열 T에서 문자열 P를 찾는 방법을 단순하게 완전탐색으로 구현해보면 이중 for문을 통해 다음과 같이 구현해 볼 수 있다. String T="CDABABKABADABABC" String P="ABABC" for(int i=0;i pattern과 pattern의 비교 text와 pattern을 비교한 것과 마찬가지로 pattern과 pattern의 비교도 비슷한 방식으로 이루어진다. 따라서 pattern과 pattern을 비교하는 알고리즘을 이해하고 나면, text와 pattern을 비교하는 알고리즘도 이해하기가 쉬울 것이다. 우선 건너뛰기 표..

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 + 이진탐색으로 해결하였다. 처음에는 이진탐색으로만 문제를 풀었는데 시간초과가 났다. 세그먼트 트리에서 노드의 범위는 1부터 1000000까지이다. 사탕의 번호가 1부터 1000000까지 존재하기 때문이다. 각 노드에는 해당 사탕의 개수가 들어있다. A = 2인 경우, 사탕상자의 사탕에 변화가 생기므로 세그먼트 트리의 update() 메서드를 실행한다. A = 1인 경우, 수정이가 요구한 순위의 사탕이 어떤 맛의 사탕인지를 ..

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 다른 삼성역량테스트 문제에 비해 쉬운 편이었으나, 문제를 잘못 이해해서 몇시간을 삽질했다. 이동하려는 위치가 파란색이면, 방향을 바꾸고 반대편으로 이동해야 한다. 이 때, 반대편이 파란색이라면 이동하지 않는다. 여기까지는 제대로 이해했는데, 만약 반대편이 흰색이나 빨간색이면 A번 말 혼자만 이동하는 것이 아니라 A번 위에 있던 말들까지 같이 이동해야 한다. 하지만 문제에는 이 부분에 대해서는 설명이 생략되어 있어서 나는 계속 A번 말 혼자서만 이동시켰다. 이 ..

1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 동적 계획법을 통한 최장 공통 수열을 구하는 문제이다. 보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다. 아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다. lotuslee.tistory.com/39?category=964787 LCS(Longest Common Subsequence) LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..

동적 계획법(Dynamic Programming) 동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다. 동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다. 동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다. 메모이제이션(Memoization) : 동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다. 그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다. 동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열은 앞의 두 항의..

Disjoint Set(분리집합)이라고도 한다. 서로 중복되지 않는(교집합이 없는) 둘 이상의 집합의 정보를 저장, 조작하는 자료구조이다. 유니온 파인드는 3가지 연산이 존재한다. make - set(x) : 초기화를 하는 연산이다. x를 원소로 하는 새로운 집합을 생성한다. 이때 생성되는 집합은 x만을 원소로 갖는다. union(x, y) : x가 포함된 집합과 y가 포함된 집합을 하나의 집합으로 합친다. find(x) : x가 어느 집합에 속해 있는지를 찾는다. 유니온 파인드를 구현하는 방법은 다양한데, 그 중에서도 가장 잘 알려진 트리를 이용한 방법을 설명할 것이다. 트리를 이용한 Union-Find 트리를 이용하여 유니온 파인드를 구현할 경우, 하나의 트리는 집합 1개를 의미하며 트리의 루트 노드..