알고리즘/백준(BOJ)
[백준/BOJ] #15961 #2535 회전초밥 [투포인터/슬라이딩윈도우/파이썬/Python]
https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 요..
[백준/BOJ]#4949:균형잡힌 세상[문자열/스택/파이썬/python]
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 내가 효율적으로 짠건지는 사실 잘 모르겠는데 내가 하는 코딩습관대로 체크플래그로 풀었다 left괄호는 플래그 1, 2 오류는 플래그 5 예제들이랑 반례들 다 통과하는데 20%쯤에서 통과가 안되서 30분정도를 애먹었는데 질문게시판에 있는 반례들이 한 6페이지까지도 다 잘 나와서 대체 뭐가 문제인지 개행문자가 문제인걸까 애를 먹고있었는데 딱 반례 '[([]])'가 no가 나와야하..
[백준/BOJ]#13565:침투[DFS/그래프/깊이우선탐색/파이썬/python]
https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 메모리 초과의 늪에서 못 빠져나오게 한 문제,,, 대체 코드에 문제가 없는데 왜 이러는건가 재귀탐색제한을 줄여도 보고 30분을 헤매었는데,, 결국 컴파일러를 pypy3가 아닌 python3 으로 바꾸니 통과했다;;; 백준에서 이런 경우가 간혹 있는데 이럴때마다 시간이 아깝고 힘 빠진다^^;; 승부는 내야하니 정답은 내야겠고,, bfs보다는 dfs로 푸는 게 더 ..
[백준/BOJ]#2078:무한이진트리[트리/수학/파이썬/python]
https://www.acmicpc.net/problem/2078 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 트리 문제라고 명시되어있지만 사실상 수학 문제다!! #2078_무한이진트리 a,b=map(int,input().split()) l=0 r=0 while a>1 and b>1: if a>b: l+=a//b a%=b else: r+=b//a b%=a l+=a-1 r+=b-1 print(l,r)
[백준/BOJ]#1406:에디터[스택/파이썬/python]
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 처음에 보고 문자열로 파싱하는게 가장 빠르다고 판단해서 풀었는데 시간초과가 떴다. 시간초과 코드 #1406_에디터 s=str(input()) num=int(input()) cursor=len(s) for _ in range(num): ctrl=list(map(str,input().split())) if cursor
[백준/BOJ]#15805:트리 나라 관광 가이드[트리/파이썬/python]
https://www.acmicpc.net/problem/15805 15805번: 트리 나라 관광 가이드 윤호는 K개의 도시들이 트리 형태로 연결되어 있는 트리 나라의 관광 가이드이다. 윤호가 새롭게 맡게 된 패키지는 트리 나라의 루트 도시에서 시작해서 모든 도시를 순회하고 오는 상품이다. www.acmicpc.net 파이썬 코드 #15805_트리나라관광가이드 from collections import Counter n=int(input()) city=list(map(int,input().split())) cntcity=Counter(city) visited=[0 for _ in range(len(cntcity.keys()))] parent=[0 for _ in range(len(cntcity.keys(..
[백준/BOJ]#9935:문자열 폭발[문자열/스택/파이썬/python]
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 처음에 보고 단순히 문자열 sequential search로 풀으니 시간초과가 났다! 역시 골드문제는 한큐에 풀리지 않지 분류를 보니 스택인 걸 보고 스택으로 바꾸었는데 또 시간초과! 반복문을 하나 줄이려면 뒤에서부터 탐색하면 된다는 걸 깨달았다. 그리고 마지막 res join문을 반복문안에서 하고 앉아있었다는 걸 깨닫구 코드를 수정하니 맞았다. 시간초과 코드(단순 순차탐색) #99..
[백준/BOJ]#2263:트리의 순회 [트리/분할정복/파이썬/python]
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 인오더와 포스트오더 (inorder, postorder)를 입력으로 받으면 preorder(프리오더)를 출력해주는 문제다. 트리의 순회방법_ 전위, 중위, 후위 순회 방식이다. 위의 트리 예시들을 읽어보면 대략적으로 그림이 그려진다. Preorder는 맨처음에 루트(부모)가 들어오고, postorder는 맨마지막에 들어온다. 이를 이용하여 처음에 루트를 구한다. Inorder는 왼쪽부터 쭉 순서대로 순회한다는 것을 알 수 ..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ/종만북/알고스팟]#1922:쿼드트리/QUADTREE [분할정복/파이썬/python/C++]
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀와 분할정복(divide and conquer)을 이용하여 푼다. #1992_쿼드트리 n=int(input()) graph=[list(map(int,input())) for i in range(n)] res="" def quad(y,x,n): global res arr=graph[y][x] notsame=False for i in range(y,y+n): brk=False for ..
[백준/BOJ]#1629:곱셈 [분할정복/수학/파이썬/python]
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복 divide n conquer 과 수학 문제다. 수학의 분배법칙을 분할정복에 적용하여 재귀로 풀어나가면 된다. 호기심에 재귀 호출 순서가 궁금해서 프린트문을 여러번 찍어보았는데 마지막 홀수인 경우, ..(10^1)%12 x 10) %12 x 10이 마지막으로 호출된다. 그러므로 12로 다 나누면 남는 건 10 * 10 숫자만 남아서 결론적으론 답이 4가 나온다. #1629_곱셈 a,b,c=map(int,input().split()) ''' 수학의 분배법..
[백준/BOJ]#1780: 종이의 개수 [분할정복/재귀/파이썬/python]
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복과 재귀를 이용하여 푸는 문제다. dfs bfs가 생각났는데 분류가 분할정복으로 되어있고 9개로 종이개수가 정해져있으므로 for문으로 돌리고 재귀를 해서 체크하면 된다. #1780_종이의개수_dividenconquer n=int(input()) paper = [list(map(int,input().split())) for _ in range(n)] res1=0 res0=0 res..
[백준/BOJ]#17413: 단어 뒤집기 2 [문자열/파이썬/python]
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 쉬운 문제라고 생각하고 후딱 풀려고 했는데.. 스톤헤드..!!! 은근히 오래 걸렸다.... delimiter(bracket) 기준으로 처음에 인덱스를 기준으로 뽑아내다가 리스트와 char 데이터타입의 충돌로 또 애먹다가.. 뒤엎고 다시 짜고.. 하다가 완성했다 결국. bracket안에서만 문자열이 뒤집히지 않으므로 신경써주고 나머지는 플래그를 두어서 그외의 경우에 ..
[백준/BOJ] #1967: 트리의 지름 [트리/BFS/python/파이썬]
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #1967_트리의 지름 from collections import deque n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(1,n): parent, child, weight = map(int, input().split()) tree[parent].append([weight, child]) tree[child]...
[백준/알고리즘] #5554:심부름 가는 길[파이썬(python)/수학]
https://www.acmicpc.net/problem/5554 5554번: 심부름 가는 길 승균이는 매일 학교, PC방, 학원에 다닌다. 반복되는 일상에 익숙해진 승균이는 이동시간을 단축해서 PC방에 더 오래 머물고 싶었다. 그래서 스톱워치를 들고 이동할 때마다 기록을 잰 후 집 www.acmicpc.net #5554_심부름가는길 total=0 for _ in range(1,5): total+=int(input()) x=total//60 y=total%60 print(x) print(y)
[백준/알고리즘] #9663:N-Queen[파이썬(python)/백트래킹]
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 문제 힌트에 퀸 노래 있는 거보고 무슨 문제지 대체..? 싶었다 체스의 퀸을 뜻하는 것이었다. N-Queen 이 문제는 백트래킹에서 대표적인 문제라고 한다. 체스판에서 퀸은 중요한 아이로! 가로 세로 대각선 거리제한 없이 쭉 쭉 뻗어 이동할 수 있는 아이입니다. 퀸 N개가 서로 공격할 수 없는 경우라 하면 가로 세로 대각선에 퀸이 겹치지 않게 하는 경우겠지요 그걸 백트래킹으로 구현해봅니다. 백트래킹은 조건..
[백준/알고리즘] #16212:정열적인 정렬 [파이썬(python)/정렬]
https://www.acmicpc.net/problem/16212 16212번: 정열적인 정렬 형준이는 수열을 하나 가지고 있다. 형준이는 수열을 정열적으로 정렬해보려 한다. 과연, 정렬할 수 있을까? www.acmicpc.net 25점을 받은 코드.. 100점 받은 코드는 어떻게 짜야하는지... #16212_정열적인 정렬 N = input() a = list(map(int, input().split())) a.sort() for i in a: print(i,end=' ')
[백준/알고리즘] #10709: 기상캐스터 [파이썬(python)/구현]
https://www.acmicpc.net/problem/10709 10709번: 기상캐스터 출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시 www.acmicpc.net 이런 구현문제는 계속 그려보거나 시뮬레이션하면서 풀면 된다. #10709_기상캐스터 H, W = map(int, input().split()) Wstring = [] for _ in range(H): Wstring.append(list(input())) sky=[[-1]*W for _ in range(1,H+1)] cnt=W for k in range(0,W+1)..
[백준/알고리즘] #1330: 두 수 비교하기[파이썬(python)/수학]
https://www.acmicpc.net/problem/1330 A,B = map(int,input().split()) print('>') if A > B else print('
[백준/알고리즘] #16953: A → B [파이썬(python)/그래프/DFS]
https://www.acmicpc.net/problem/16953 #16953_A->B from collections import deque A, B= map(int, input().split()) def dfs(x,y): q=deque([(x,y)]) while q: num, cnt = q.popleft() if num == B: return cnt if num * 2