개발자 퉁이리

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 분할 정복 재귀 ⊙ 문제 접근 과정 분할 정복 문제....... 별찍기가 이렇게 어려운 문제였나 row%3=1이고 col%3=1일때는 공백을 출력해줬다. ⊙ 문제 풀이 #include using namespace std; void star(int i, int j, int N) { if (i % 3 == 1 &&..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 for문 2개를 사용하여 이중 list의 각각의 index를 만져줬다. 반복문 속의 조건문은 총 3가지로 나눴다. 가장 왼쪽에 있을 때, 가장 끝에 있을 때, 그리고 나머지. ⊙ 문제 풀이 N=int(input()) T=[] for _ in range(N): T.append(list(map(int,input().split()))) for i in range(1,N): f..

https://www.acmicpc.net/problem/10950 10950번: A+B - 3 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 구현 사칙연산 ⊙ 문제 접근 과정 반복문 밖에 반복할 횟수(T)를 입력받고 그만큼 A+B 값을 계산해 출력해주자 ⊙ 문제 풀이 T=int(input()) for _ in range(T): A,B= map(int, input().split()) print(A+B) ⊙ 결과 ⊙ 마무리 NONE 좋아요는 로그인하지 않아도 누를 수 있습니다!

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 스택 ⊙ 문제 접근 과정 case로 구현하려 했는데 c++로는 쉽지 않아서 if문으로 해결했다. 혹시 stack을 C++에서 어떻게 사용하는지 헷갈려하는 분들을 위해 아래에 정리해놨다! ⊙ STACK STACK은 LIFO이다. LIFO는 LAST IN FIRST OUT, 즉 나중에 들어온 원소가 가장 먼저 나..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 ⊙ 문제 접근 과정 처음 접근할 땐, vector 두 개를 사용하고 sort에 또 다른 함수를 만들어서 정렬해주는 바람에 코드 길이가 길었지만 더 효율적으로 문제를 푸는 방법이 있었다. 아래에서 소개하겠다. max함수를 이용하면 문제를 쉽게 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 index 0 = red index 1 = green index 2 = blue 배열을 사용했다. 다 더하고 더한 N번째의 최솟값을 출력하였다. ⊙ 문제 풀이 #include using namespace std; int N; int result=0; int dp[1001][3]..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 브루트포스 알고리즘 백트래킹 ⊙ 문제 접근 과정 좌표 코드를 만들고 아래로 내려가면서 탐색하는 코드를 구현해줬다. ⊙ 문제 풀이 #include using namespace std; int N; int result=0; int chess[16][16]; int dy[3]= {-1,-1,-1}; int dx[3]= {-1,0,1}; int down(int..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 문자열 ⊙ 문제 접근 과정 LCS 알고리즘 문제다. LCS는 번역하면 최장 공통 부분 문자열이다. 전에 다뤘던 LIS 최장 증가 부분 수열과 유사하다. LIS는 다이나믹 프로그래밍(DP)을 기반으로 알고리즘이 구성되어있는데 LCS도 마찬가지이다. DP를 이용하여 구현하면 공..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 규칙을 찾고 점화식을 세우자! N=1, 1개 N=2, 3개 N=3, 5개 N=4, 11개 N=5, 21개 점화식 = (N-2)*2 + (N-1) ⊙ 문제 풀이 arr= [0,1,3] for i in range(3,1001): arr.append(arr[i-2]*2+arr[i-1]) N=int(input()) print(arr[N..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 자료 구조 문자열 파싱 덱 ⊙ 문제 접근 과정 deque으로 문제를 풀었다. 그리고 boolean을 적극 활용했다. 앞 뒤 값을 사용한다고하면 deque가 자동으로 생각나야한다. 기억하자 queue는 단방향, deque는 양방향 첫 시도 코드는 시간 초과가 떴다. 명령어에 R이 나올 때마다 reverse()를 사용하면 제한 시간인 1초 안에 절대 풀지 못한다. 명령어의 수가 최대 100,..