시나위

1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 요약 무한 수열 A의 N 번째 값 구하기 A0 = 1, Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) (⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.) 접근 1. 구현 주어진 조건에 대해 구현하기. N 에 대해서 구해야하므로 Top Down 방식이 나을듯 했다. 그리고 max(N) = 10^12 이므로 꽤 많은 연산이 있을 것이고 중복 되는 값이 있을 것이므로 Dynamic Programming으로 구현한다. DP을 위해 배열을 사용해서 메모리를 잡으면 공간복잡도는 O(N)이나 최대값이 4*10^12이므로 메모리 제한을 초과한다. -> 해시(unordered_map)를 사용해서 필요한 값만 저장..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 요약 동전이 보드 위에서 움직일 수 있는 최대횟수 구하기 접근 1. 생각의 흐름 1 - BFS 보드가 이차원이고 모든 방향을 탐색하면서 최대로 움직이는 횟수를 파악해야하므로 그래프 탐색중 BFS를 사용해야할 것 같았다. BFS는 특정 지점까지의 최소 거리를 구할 때 사용하는데 이 경우에서도 충분히 사용할수 있을 거라고 생각했다. (멈추는 지점까지의 최소 거리를 구하면 최대로 움직인 거리를 구하는 거랑 같을 거니까) 간단하게 적어보면 다음과 같다. (0,0)..

Softeer 자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로 softeer.ai 문제 요약 자동차별로 교차로를 통과하는 시간 출력하기 우측 도로에 자동차가 없어야 통과할수 있음 접근 1. 머리에 생각나는 대로 알고리즘 작성 A~D까지 도로 Queue 생성, 입력에 대해서 도로별로 시간을 push 출력을 위해 queue도 생성 Time(t) = 0 부터 시작해서 매 초 각 도로 확인 A~D 도로의 첫번째 차가 도착한 시간 확인. 차 시간이 현재 시간보다 작거나 같은 경우 오른쪽에 차가 없으면 체크 나머지 경우 패스(현재시간보다 크거나, 작거나 같지만 오른쪽에 차가 있는 경우) 네 도로 ..

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 요약 비교 상태를 사용하여 줄 세우기, 위상 정렬 접근 1. 트리 트리를 생성한다음 최상위 노드에서 후위 순회하는 방식으로 접근했다. 이 접근방식을 구현할때 반례가 바로 떠올라 안될거같아서 적당히 구현했다. #define MAX_SIZE 32000 int visit[MAX_SIZE + 1]; // 128kb int parent[MAX_SIZE + 1]; // 128kb void postorder(int index,..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 요약 N개의 물건으로 가방을 싸는 문제 최대 무게 K를 넘지 않으면서 가방에 든 물건이 최대 가치를 지녀야한다. 접근 1. Greedy 무게가 높고 가치가 높은 순으로 정렬한 뒤에 하나씩 넣으면서 해도 정렬을 한뒤에 풀어도 괜찮은지 고민해봤지만 풀리지 않는 예제가 있어서 바로 넘어갔다. 2. Bruteforce 그 다음 쉬운 방법인 브루트 포스 이다. 모든 물건에 대해서 넣거나 넣지 않거나 모..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 요약 수열 A에서 증가 부분 수열 중 합의 최댓값 찾기 접근 1. 규칙찾기 알고리즘 규칙찾기 새로 알게된 것 dp 너무 어려운데..? 전체 코드 #include #include // max #define MAX 1000 using namespace std; int N, answer; int arr[MAX]; int memo[MAX][MAX]; void printMemo(int size) { for (..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 요약 3xN 크기의 벽을 2x1, 1x2의 타일로 채우는 경우의 수 접근 1. 규칙찾기 n이 홀수면 만들수 없음 n이 짝수인 경우 만들수 있음. n= 2: 3개 n= 4: (n = 2인 타일에 n = 2인 타일을 추가하는 경우) + (n=4인 타일을 추가하는 경우, 새로운 타일) 3*3 + 2 개 = 11개 n= 6: (n = 4인 타일에 n = 2인 타일을 추가하는 경우) + (n = 2 인 타일에 n=4인 타일을 추가하는 경우) + (n = 6 인 타일을 추가하는 경우, 새로운 타일) - (중복값 제거) 11*3 + 2 + 2*3 = 33 + 2 + 6 = 41개..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 요약 스도쿠 정답을 찾으면된다. 행과 열, 3X3 안에 1~9가 중복없이 들어가야한다. 접근 1. Brute-force 숫자를 넣어야하는 자리수는 최대 81개이고 1부터 9까지 모든 값을 넣어서 확인하려면 981 이 된다. O(232) 는 대충 42초 정도 걸리는데 이 값보다 크므로 이 방법으로 풀수 없다. 물론 0인 위치에서만 확인하면 되지만 찾아야하는 위치가 9개 이상이면 3초가 넘으므로 입력값을 알지 못하면 풀수 없다. 2. Backtracking 백..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 손님들이 주문한 단품 메뉴로 코스요리(조합)를 만든다. 코스 요리는 단품 두개 이 상으로 이루어져있다. 코스 요리의 길이(단품 메뉴의 개수)를 보고 그 중에 가장 많이 선택된 조합을 반환한다. 접근 모든 손님들이 주문한 단품 메뉴로 모든 조합을 만들어야한다. 조합을 만들 때 반복문, 라이브러리, 백트래킹으로 구현할수 있다. 1. 조합만들기 - 반복문 반복문을 중첩해서 사용하면 쉽게 조합을 만들수 있다. 예를 들면 ABCDE에서 3개의 원소를 가지는 조합을 만들기 위해선 다음과 같이 짜면 된다. st..

2641번: 다각형그리기 모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 www.acmicpc.net 문제 요약 처음 주어지는 모양수열로 만들어진 도형과 같은 도형이 나오는 수열을 찾는 문제이다. 모양수열은 방향을 가리키는 숫자 (1: 우, 2: 상, 3: 좌, 4: 하)로 이루어진 수열이다. 회전이나 뒤집었을때 같은 도형은 다른 것으로 생각한다. 접근 1. 쉬운 도형을 직접 그려서 규칙 확인 크기가 1인 정사각형의 모양수열을 확인했다. 좌측 상위의 점을 시작점으로 잡았을 때 시계방향으로 도는 모양수열은 1-4-3-2가 된다. 같은 시작점이고 반시계방향인 모양수..