본문 바로가기

전체 글

 (53)
백준 티어 설정 + 추가 꿀팁 우선 백준에 로그인 한뒤 설정을 해줘야한다. https://solved.ac/ solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 난이도 및 티어 정보 제공 solved.ac 위 링크로 들어가서 아래와 같이 해주면 된다. 로그인을 누르고 완료하면 티어를 볼 수 있다.! 추가로 해두면 좋은 설정들을 설정해보자. 1. solved.ac티어 보기를 선택하면 문제 왼쪽에 티어가 나타나게 되고 2. solved.ac티어 이름을 선택하면 괄호 안에 적혀있듯이 문제 제목 하단에 티어가 보이게 된다. 3. 알고리즘 분류는 이 문제에 어떤 알고리즘이 쓰였는지 보여주는 부분이다.
백준 16235 나무 재테크 파이썬 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 재미있는 구현 문제였다. 하지만 파이썬에서는 시간제안이 좀 빡빡했던거 같다. 원래 봄, 여름, 가을, 겨울을 따로 구현했었고 가을에 나무를 추가할때 sort를 썼다. 시간초과가 나서 봄 + 여름을 합치고 제출했는데 또 43%부분에서 시간초과가 났다, 마지막으로 deque를 사용해 작은것 부터 양분을 먹을 수 있게 sort부분은 appendleft(1)로 고쳐주니 겨우 통과했다. i..
백준 1010 다리놓기 파이썬 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 꼬이지 않게 다리를 배치하기 위해서 조합을 사용하는 되는 문제였다. from itertools import combinations n,m = map(int,input().split()) n,m = min(n,m),max(n,m) s=list(combinations([i for i in range(m)], n)) print(len(s)) 위와 같은 방법으로 조합을 만들어서 계산하게 되면 시간초과가 ..
백준 1780 종이의 개수 파이썬 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 종이를 9개의 부분으로 나눈뒤 탐색을 해주면 되는 간단한 문제였다. *한가지 주의할 점은 pypy로 제출해야 했고, 나누기전 초기 종이에서도 한번 탐색을 해줘야 하는 것이다. (처음부터 성분이 1개일때.) def ch(s,a,b,c,d):#9개의 부분중 한 부분을 탐색하는 함수이다. global re ch = set() t = 0 e=[] for i in range(a,b): e.app..
백준 17822 원판 돌리기 파이썬 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net *중요한 포인트* 1. 바로 deque를 떠올리는 것 (방향에따라 appendleft(pop()) // append(popleft()))해주기 위해 2. x 배수의 원판만 돌아간다는 것. 3. 숫자 삭제와 증감은 모든 원판이 다 돌아가고 일어난다는 것 (제일 중요) 4. 원판 안의 모든 숫자가 0일 수 있다.(런타입 에러 관련) 코드 설명은 코드 주석으로 하겠습니다. from co..
백준 14246 K보다 큰 구간 파이썬 반례 1개 O https://www.acmicpc.net/problem/14246 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 처음에는 시간 복잡도를 생각하지 않고 한번 작성해봤다. O(N^2) (결과는 당연히 시간 초과.) n = int(input()) s = list(map(int,input().split())) k = int(input()) sums = 0 re =0 for i in range(n): sums = s[i] for j in range(i+1,n): sums+=s[j] if sums>k: re+=(n-j) break print(re) 위에 코드에서도 알 수 ..
백준 16236 아기상어 파이썬 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 간단한 BFS문제에 우선순위가 추가된 문제였다. from collections import deque import heapq def bfs(q): global re vist = [[False]*n for _ in range(n)]#방문체크 h=[]#우선순위 연산을 해줄 heapq while q: x,y,c,size,up = q.popleft() for k in range(4): nx = x..
백준 17299 오등큰수 파이썬 문제 설명 O heapq사용 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 해석부터가 어려웠던 문제였다. 뒤에 해석까지 있었으면 더 이해하기 편했을거 같다. A4가 왜 2가 되냐면 A[4~n] 까지 나온 수를 보면 3, 4, 2, 1이 나왔음을 알 수 있다. (굵은 숫자가 비교 값) 차례대로 1, 1, 2, 3인데 비교 대상은 1이다. 따라서 1보다 큰 수 중에 가장 왼쪽에 있는 값(비교 값 보다 큰 수가 처음 나온 위치의 수 )을 해줘야하는데 그 수가 2번나온 2여서 A4는 ..

티스토리툴바