시나위

문제 요약 현재 탑의 크기보다 큰 탑 중 왼쪽으로 가장 가까운 탑찾기 접근 1. 생각의 흐름(Greedy) 출력 아무것도 없을때 0 값이 있으면 해당 인덱스 값 출력 -> (value, index ) 같이 넣어야할듯 저장한 값보다 값이 크면 큰값이 나올때까지 pop 저장한 값보다 값이 작으면 push 전체 코드 #include #include #define MAX_N 500000 using namespace std; int N; int arr[MAX_N]; int main() { cin >> N; for (size_t i = 0; i > arr[i]; stack s; // value, index for (size_t i = 0; i < N; i++) { if (s.empty()..

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 요약 두 배열이 주어졌을때 각각의 배열로 만들수 있는 부배열의 합이 T가 되는 부배열쌍의 개수 구하기 접근 1. 생각의 흐름 각 배열의 부배열합을 구해서 저장해야한다. 원소가 1개인 것부터 모든 원소가 들어간 것 까지의 부배열을 만들고 그의 합을 저장했는데 누적합을 사용했다. void makeArr( vector& arr, vector& cumArr, int size ) { a..

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 백..

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

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다. 이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다. 제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다. 3 1 100 100 100 100 100 1 100 100 위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택..

https://www.acmicpc.net/problem/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 상당히 쉬운 브루트포스 문제이다. 0,0,0 부터 각 방이 가질수 있는 최댓값까지 돌리는 방법으로 구현했다. def main(): *room, total = map(int, input().split()) for i in range((total // room[0]) + 1): tmp1 = room[0] * i for j in range((total // room[1]) + 1): tmp2 = ..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 와샬 알고리즘을 사용해서 풀면된다. 뒤집지 않고 갈수 있으면 0을 넣고 한번이라도 뒤집어야한다면 1을 넣어서 초기화한다. 이후 floyd-warshall 알고리즘(i에서 k를 거쳐 j를 가능 방법)을 사용해서 최솟값으로 갱신하면 된다. import sys; input = sys.stdin.readline def floyd_warshall(n, visit): for k in range(1..

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 문자열은 파이썬이 편하다. 마지막에 f가 있을거라 예상해서 f를 기준으로 단어를 나눴다(인덱스만 저장). 그리고 각각의 인덱스를 기준으로 4의 배수인지 확인하면 wwwoolllfff 같이 중간에 하나 빠져있는 단어들을 제거할수 있다. 그다음은 wlof 와 같은 단어를 제거한다. 나누어진 단어의 길이를 4로 나누면 한 단어당 나와야하는 알파벳의 갯수가 나온다. 이 개수로 wolf 각각 문자열을 곱하고 더해서 단어를 만들고 원래 기존의 단어와 비교하면 제거할수 있다. 여기까지..

https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 동적계획법으로 누적합을 사용하는 문제이다. 출석체크 한 사람을 구한뒤에 출석하지 않은 학생을 하나하나 찾아서 계속 시간초과가 걸렸다. 누적합으로 구한뒤에 구간별로 출력하니 통과. import sys; input = sys.stdin.readline # 0 입력 N, K, Q, M = map(int, input().split()) sleep = set(m..

https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N 0: if owned[x]: land = x x >>= 1 return land N, Q = map(int, input().split()) owned = [False for _ in range(N + 1)] for i in range(Q): x = int(input()) owned_land = check_owned(x, owned) if not owned_land: owned[x] = True print(owned_land) #include using namespace std; bool owned[(1 >= 1;..