꾸준함이 성장을 도모한다! 꾸준함이 성장을 도모한다!

1. 문제https://www.acmicpc.net/problem/9935  2. 풀이1. 문제의 핵심은 시간복잡도! 2. 실패코드- 기본적인 slicing을 통해 코드를 구할 수 있음- n의 범위를 따질 때, O(n * ( n - len(boom) ) + slicing으로 나오는 시간복잡도. => 기준 초과=> 1%에서 시간초과가 난다 3. 성공코드- stack에 담아가며 stack의 길이가 len(boom)이상이며, stack[-len(boom):] 이 boom이랑 같을때마다 pop()-> O(N)의 시간복잡도를 갖는다는 걸 알 수 있다. 3. 코드1. 시간 초과 코드string = input()boom = input()b = len(boom)while True: flag = False i..

1. 문제https://www.acmicpc.net/problem/6987  2. 풀이[ 실패 풀이 코드 부분 ]1. 한 국가당 무승부 + 승 + 패의 수가 5여야 한다2. 무승부가 나온다면 무승부의 수는 짝수이면서, 최소 2개 국가가 무승부를 기록해야한다3. 승 수 == 패 수위의 3가지 조건만 있다고 간과하였습니다. 이 과정에서 질문 게시판을 보았고 내가 생각했던 반례보다 훨씬 더 많은 반례가 있다는 것을 알게되며, 백트래킹으로 풀어야 함을 알게됐습니다. 예를 들면,1. 한팀이 5번 이기면 다른 팀들은 한번씩 필수로 져야한다2. 한팀이 5번 패하면 다른 팀들은 한번씩 필수로 이겨야한다-> 1번과 2번의 이유로 5승한팀이 2개 이상, 5패한 팀이 2개 이상이 있을 수 없다.등등 반례가 무수히,,, 하지..

1. 문제https://www.acmicpc.net/problem/3085  2. 풀이중요 point 1) n*n 모든 값들을 4가지 방면으로 switching 해본다.-> change() 로 값이 다른지 확인하고 boolean으로 응답하기 중요 point 2) switching이 된다면, 같은 값을 가진 가장 긴 행/열을 구할때, 현재 2차원 index로부터 뒤의 모든 값들을 확인하지 말고 바로 앞에 있는 값이랑만 비교하면서 max값, tmp값 update 해주기-> calc() 참조! 중요 point 3) switching 하고 max_val 값 update했으면, 다시 원래자리로 복구해주기  3. 코드n = int(input())arr = [ list(input()) for _ in ra..

문제https://www.acmicpc.net/problem/14719문제 풀이법1. 처음과 끝에 벽이 있어야만 물을 채울 수 있다.2. 관점의 문제이다. [ 현재 기점으로 좌우를 비교하냐? 현재 기점으로 뒤만 비교하냐 ]- 나의 경우, 실패 사례는 현재 기점으로 뒤만 비교했다 문제 코드[ 실패 사례 ]h,w = map(int,input().split())blocks = list(map(int,input().split()))cur_height = blocks[0]amount = 0among_block = []for i in range(w): flag = False if blocks[i] cur_height: flag = True cur_height = bloc..

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 1. 조건이 복잡하지 않아서 따라 하기만 하면 된다. 2. 고민할만한 점은 공기청정기가 직사각형의 둘레를 따라 시계 / 반시계 방향으로 바람이 분다는점이다. - 범위를 벗어날때 direct를 변경해주면 된다. - 앞의 내용과 이전의 내용을 바꿔주면 된다 코드 import sys n,m,t = map(int,input().split()) up,down = -1,-1 # 시계방향 dxs,..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 팁 1. 처음에 작성한 코드는 먹을 수 있는 물고기들을 매번 구하면서 가장 가까우며, 혹은 가장 위 / 가장 왼쪽 기준으로 선택하여 한번에 거리들을 구하는 방식으로 갔다.. ( 아직도 왜 틀린지를 모르겠지만, 계속 틀려서 수정 -> 아시는 분은 댓글 부탁드려요 ㅠ ) https://www.acmicpc.net/board/view/139274 글 읽기 - 왜 틀렸을까요?? 댓글을 ..

문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 팁 1. 이 문제는 단순히 조건을 따라가면서 풀면 되는 문제인데, 가장 중요한 점은 시간복잡도 이다. -> 나는 처음에 단순히 3차원 배열 만들면서 배열을 초기화 시키면서 했다 ( 가장 아래에 처음 코드를 넣어 놓겠다 ) -> 읽어보면 초기화를 엄청 시키면서 했는데, 나는 이 부분이 시간초과의 원인이라고 생각한다 ( 테코는 다 맞음 ) 2. 시간 초과를 줄이기 위해서 한..

문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 팁 1. 문제를 보자마자 모든 경우의 수 ( cctv 마다 각자 회전하여 나오는 영역의 수 )를 구하는 문제라는 걸 알고, 백트래킹과 조합을 생각했다 2. 백트래킹을 푸는데 나는 계속 어느 시점에 초기화를 해야하는지 몰랐다.. 아시는 분은 여기 답좀 남겨주세요,.... https://www.acmicpc.net/board/view/138803 글 읽기 - 어떻게 수정을 해야할..