작은개발자

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 다이나믹 프로그래밍 방식을 사용해서 풀 수 있다. n을 1과 2의 합으로 나타내는 ..

📌 Dynamic Programming 복잡한 문제를 여러 개의 문제로 나누어 푸는 방법 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 대표적 예시로 피보나치 수열이 있다. 피보나치 수열 피보나치 수열 점화식: F0​=0, F1​=1, Fn+2​=Fn+1​+Fn​ 다음과 같이 재귀함수를 사용하여 코드를 구현할 수 있다. def fibonacci(num): if num == 1 or num == 2: return 1 return fibonacci(num-1) + fibonacci(num-2) 단순 재귀함수로 구현했을 때, 동일한 함수가 반복적으로 호출되는 것을 볼 수 있는데 시간복잡도가 O(2^N)으로 N값이 커짐에 따라 연산 수행시간이 기하급수적으로 늘어난다. 동적 계획법을 사용하면 이러한 반복적인..

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 ..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한..

백준 시간초과 백준에서 알고리즘 공부를 하다보면 시간초과로 애를 먹을 때가 많다. 시간초과 문제 고치다가 내 시간만 초과되는 상황.. 막상 다 풀어보면 분명 다른 사람들과 몇 줄 차이 안나는데 시간차이가 많이 나는게 마음에 안들어서 도대체 뭐가 다른지 찾아봤다. 우리 모두의 시간은 소중하니까 시간을 단축할 수 있는 방법들 중 몇 가지를 가져왔다. 1. input()보다 sys.stdin.readline()이 더 빠르다. 백준 문제를 많이 풀어본 사람들은 많이 아는 팁이다. input() 내장함수 word = input("단어를 입력해주세요") input이 호출되면 Promt message를 화면에 출력하고 사용자의 입력을 기다린다. 사용자가 키를 하나씩 누루면 데이터가 버퍼에 들어가는데, 개행문자(줄바꿈..

📌 Label smoothing이란? Hard target(0또는 1)을 soft target(0과 1사이)으로 만드는 것 Multi-class 분류 문제에서 사용되는 라벨은 일반적으로 원-핫 벡터 (one-hot vector)를 사용합니다. 원-핫 벡터는 정확히 하나의 클래스만 표현하는 방식으로 정답에 해당하면 1, 나머지는 0으로 넣는 방식입니다. Label smoothing 기법은 정답 클래스의 비중을 약간 줄이고 나머지 클래스의 비중을 늘리는 기법으로 수식은 다음과 같습니다. y_kLS = y_k(1-alpha) + alpha/K K개의 클래스에 대해 smoothing 파라미터를 alpha라고 할 때, hard label y_k를 soft label y_kLS로 만들 수 있습니다. 예를 들면 K ..

❓ 인공지능(AI)이란? 인간의 지능을 모방하여 지적 능력을 기계가 구현하는 것입니다. ❓ 머신러닝은 무엇인가요? 알고리즘을 이용하여 데이터를 분석하고 학습하며 그 내용을 기반으로 판단이나 예측을 합니다. ❓ 딥러닝은 무엇인가요? 머신러닝에 포함되는 개념으로 여러 층을 가진 인공신경망을 사용하여 학습합니다. 딥러닝은 기계가 사람의 도움 없이 결정을 내릴 수 있도록 해주는 신경망을 사용합니다. 하지만 신뢰할 수 있는 결과를 얻기 위해 많은 양의 데이터가 필요하며, 높은 시스템 성능이 요구되고 처리 시간이 오래 걸린다는 단점이 있습니다. ❓딥러닝과 머신러닝의 차이에 대해 설명해주세요! 딥러닝과 머신러닝의 가장 큰 차이점은 기계가 사람의 도움을 받는가의 여부입니다. 딥러닝은 데이터를 스스로 학습할 수 있는 반..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다...

비트 마스크 (BitMask) 컴퓨터의 연산방식을 이용하여 정수의 이진수 표현을 자료구조로 쓰는 기법 *비트 (bit)란? 컴퓨터에서 다루는 최소 단위로 0과 1로 이루어짐 장점 빠른 수행시간 간결한 코드 더 적은 메모리 사용 비트 연산자 c = a & b # AND 000101 & 000011 = 000001 c = a | b # OR 000101 | 000011 = 000111 c = a ^ b # XOR 000101 ^ 000011 = 000110 c = ~a # NOT ~000101 = 111010 c = a b # SHIFT 000101 >> 000011 = 000000 1. AND 연산 대응하는 두 비트가 모두 1일 경우 1, 아니면 0 2. OR 연산 대응하는 두 비트가 모두 0일 경우 0,..