분류 전체보기166 [순서론(Order theory)] Strict Weak Ordering의 개념 포스트를 읽으실 때 참고하실 점프로그래밍에 대한 깊은 이해를 쌓고자, 개인적으로 필요한 수학적 지식들을 간략하게만 기록하기 위한 포스팅입니다. 단순한 수준의 프로그래밍을 하기 위해서는 필요하지 않은 내용이 다수 포함될 수 있습니다.만약 포스팅에 잘못된 내용이 있다면 댓글이나 이메일을 통해 알려주시면 수정하겠습니다. 감사합니다. Strict weak ordering집합 $S$에 대하여 다음의 4 가지 조건을 만족하는 동차 관계(homogeneous relation) $strict weak ordering이라고 한다. 비반사성(irreflexibility): 집합 $S$에 속하는 모든 원소에 대해 $a 추이성(transitivity): 집합 $S$에 속하는 원소 $x, y, z$에 대해, $x 비대칭성(a.. 2023. 5. 30. [Baekjoon] 2908번: 상수 https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 문제 해결 과정 착안 숫자를 뒤집어 읽었을 때의 대소 비교는 주어진 숫자들을 일의 자리의 수부터 차례로 십의 자리 수, 백의 자리 수를 비교하는 과정을 통해 빠르게 확인할 수 있으므로 이를 활용하여 문제를 해결하고자 하였다. * 문제에서 주어지는 숫자가 반드시 세 자리 숫자이며, 서로 다른 숫자라는 조건이 있기 때문. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #includ.. 2023. 5. 29. [Baekjoon] 2675번: 문자열 반복 https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 문제 해결 과정 착안 문제에서 요구하는 것과 같이 주어지는 반복 횟수와 문자열에 대해, 문자열 내의 문자 별로 반복 횟수 만큼 단순하게 반복하여 출력하는 코드를 작성하고자 하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; int main() { ios::sync_with_stdio(.. 2023. 5. 28. [Baekjoon] 10809번: 알파벳 찾기 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 문제 해결 과정 착안 요소의 수가 26 개인 배열을 만들어, 알파벳 순으로 각 인덱스를 지정($a : 0, b : 1, \cdots, z : 25$)해 처음 나온 위치를 저장하고자 하였다. 알파벳이 중복으로 나오는 경우는 이미 처음 나온 위치가 $-1$ 이 아닌 값으로 저장되어있으므로 계산하지 않고 건너 뛰도록 구현하고자 했다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오.. 2023. 5. 28. [Baekjoon] 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 해결 과정 착안 도시들이 각각 서로 다른 번호로 구분되고(정수형 데이터), 도시들 사이의 연결 여부가 문제에서 주어지고 있으며 여행 경로에 해당하는 도시를 방문하기 위해 다른 도시를 중복으로 방문이 가능하다. 여행 경로가 주어졌을 때 시작 도시에서 경로 내에 있는 도시들을 방문이 가능한지의 여부만 확인하면 되는 문제이므로, 트리 또는 그래프의 구조를 활용해 탐색을 빠르게 수행하는 것을 목표로.. 2023. 5. 26. [Baekjoon] 1904번: 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 해결 과정 착안 처음에는 문제를 해결할 마땅한 방법이 잘 안떠올라서 모든 가능한 문자열을 실제로 전부 구해보고(브루트 포스, 무차별 대입) 길이가 $N$이 될 때 Count를 하나씩 늘리는 방식으로 프로그래밍 했는데, 문자열이 길어짐에 따라 분기가 크게 늘어나므로 너무 많은 수의 재귀 호출이 일어나 메모리 초과로 실패했다. 이런 상황을 어떻게 해결할지 한참 고민하다가 아래와 같이 단계를 나누고, .. 2023. 5. 25. 이전 1 ··· 17 18 19 20 21 22 23 ··· 28 다음
