joseph0528 코딩 블로그

solved.ac 티어 : 플래 4 www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제도 보자마자 버거운 버거라 응요이라는 거를 알 수 있다 그렇기 때문에 이것도 버거운 버거를 풀면 날먹이다. 이문제는 변경이 없는 대신 올바른 괄호 문자열인지 확인하는 것이 입력으로 주어진다. 그러므로 변경 부분을 지우고 입력을 받은 값을 구간에 넣어주면 끝이다. #include #include using namespace std; typedef long lo..

solved.ac 티어 : 플래 2 www.acmicpc.net/problem/17407 17407번: 괄호 문자열과 쿼리 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다. 버거운 버거를 풀고 오면 거저로 얻는 문제이다. 버거운 버거:joseph0528.tistory.com/8 BOJ 19851(버거운 버거)풀이 세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무..

solved.ac 티어 : 플래 4 www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net 이문제는 입력에 음수가 있기 때문에 평범한 이분 매칭으로는 안된다. 그렇다고 음수에다가 값을 더하려고 해도 범위가 -10^6

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 이문제는 dp이다. 점화식은 dp[n-1][l-1][r]+dp[n-1][l][r-1]+(i-2)*dp[n-1][l][r]이다. dp[n-1][l-1][r]는 재일 왼쪽 막대를 뺐을 때이고 dp[n-1][l][r-1]는 재일 오른쪽 막대를 뺐을 때이고 dp[n-1][l][r]*(i-2)는 양쪽 막대를 제외한 나머지 막대를 배치할 수 있는 경우의 수이다. import ..

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/7894 7894번: 큰 수 많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다. 수가 주어지면, 그 수의 팩토리얼의 자리수를 구하 www.acmicpc.net 이문제는 log10(1)+log10(2)+log10(3)... log10(m) 이 답인데 처음에 그냥 2중 반복으로 하면 시간 초과 날 거 같아서 log10(1)+log10(2)+log10(3)... log10(m) = log10(m!)인걸 이용해서 팩토리얼을 최대한 짧게 구해서 하려고 했지만 O(M/2)만큼 걸려 시간 초과가 나서 그냥 2중 반복으로 했더니 맞았다;; import math..

solved.ac 난이도 :플래 3 www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 이문제는 일반 세그 레이지에서 +를 XOR(^)로 바꿔주면 된다. 하지만 이렇게만 바꿨을 경우 틀리게 된다. tree[n]=lazytree[n]*(e-s+1); 이거를 if((e-s+1)%2!=0){ tree[n]^=lazytree[n];//*(e-s+1); } 이렇게 바꿔주면 된다. 저렇게 바꿔 주는 이유는 어떤수를 a라고..

어떤 분의 추천으로 만들게 됐다. 밑에 영상을 보고 플레이 방식을 알고 다시 글을 보기 바란다. https://www.youtube.com/watch?v=mFGevho4OLY 이 게임이고 구현은 생각보다 간단했다. 여기서 회색 상자는 벽이고 파란색 원은 도착지점이다. 빨간색 원은 도착지점 안에 넣어야 되는 말(?)이고 초록색은 들어가면 안 되는 말(?)이다. 여기서 화살표 키로 이동할 수 있고 처음에 5*5 크기의 맵을 입력 하라고 뜬다. 이때 1은 빈 공간, 2는 벽, 3은 초록색 원, 4는 빨간색 원, 5는 파란색 원이다. 파란색 원은 한 개만 넣어야 되고 초록색 원이랑 빨간색 원, 벽의 개수는 자유이다. 하지만 가끔씩 깰 수 없는 맵을 입력 했을 경우 다시 시작하면 된다. 이 게임도 조금씩 업그레이..

오목 만들고 싶어서 오목을 만드는 중이다. 아직 돌 놓기와 승패가 나는 거밖에 구현을 안 해놨다 이제 AI도 넣을 것이다. (지능은 좋지 못할 거 같다) 그리고 게임이 끝나기 전 판정 시스템도 내일이나 이번 주 안으로 넣을 예정이다. import sys import random import pygame import time from math import * from tkinter import * import tkinter.messagebox from pygame.locals import QUIT,KEYDOWN,K_LEFT,K_RIGHT,K_UP,K_DOWN,Rect,MOUSEBUTTONDOWN,K_SPACE pygame.init() FPSCLOCK = pygame.time.Clock() SURFACE =..

solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/1574 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼 www.acmicpc.net 이문제는 한 행 과열에 단 한 개의 룩을 놔서 최대한 많이 놓은 개수를 출력하는 문제이다. 정말 간단한 이분 매칭 문제다. 행과 열에 한 개만 놓을 수 있다는 것은 행 또는 열을 잡고 자신이 놓을 수 있는 곳에 이분 매칭을 해주면 된다. 하지만 여기서 빈칸이 생기는데 그래도 공격이 막히지는 않으니 입력 위치가 아니면서 놓을 수 있는 곳들을 이분 매칭 해주면 된다...

solved.ac 난이도 : 플래 5 www.acmicpc.net/problem/2505 2505번: 두 번 뒤집기 첫줄에는 숫자판의 크기를 나타내는 정수 N (5≤N≤10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다. www.acmicpc.net 이 문제의 풀이는 의외로 간단하다. 이문제 조건에서 한 번만 뒤집는다고 바꿨을 때 어떻게 하면 구할 수 있을까? 한 번만 뒤집는 경우 해당 값이랑 해당 위치가 다를 경우 해당 위치랑 같은 값을 찾아서 반전을 시켜주면 된다. 이걸 두 번 뒤집기에 똑같이 적용해서 값이 다를 경우 찾아서 바꿔주면 된다. 하지만 이렇게 했을 경우 반례가 생긴다. 하나의 예를 들어보면 10 1 8 7 6 ..