www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net vis 배열을 3차원으로 만들고 세 번째 인자 c가 1이면 뚫은 벽, 아니면 뚫지 않은 벽이다. 벽을 뚫을 필요가 없을 때는 일반적인 bfs를 해주고 이미 한번 뚫은 뒤에는 (c가 1인채로 온 경우에는 현재 위치가 0인 경우에만 지나갈 수 있다) 벽을 뚫을 경우에는 현재 위치가 1(벽)이고 c가 0인 경우이다. import sys input=sys.stdin.readline from c..
www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net import sys from math import sqrt input=sys.stdin.readline d={'*':2,'/':2,'+':1,'-':1,'(':0,')':0} q=[] s=input().strip() for x in s: # 알파벳 출력 if x not in d: print(x,end='') #왼쪽 괄호 elif x=='(': q.append(x) # 오른쪽 괄호시 왼쪽 괄호 나올때까지..
www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net m.blog.naver.com/PostView.nhn?blogId=rdd573&logNo=221270230610&proxyReferer=https:%2F%2Fwww.google.com%2F 위 글을 참고하여 풀었다. 골드 바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것이다. 따라서 홀수만 ! 체크해 주면 된다 또 a,b의 범위가 워낙 커서 문제가 되는데 에라토스테네스의 체로 소수를..
www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net heapq 모듈을 쓰면 heappop할 때 기본 작은 순서대로 반환하는데 -를 붙이면 큰 값이 가장 작아지므로 그렇게 넣은 뒤 반환한 값을 다시 -를 붙여서 되돌린다 import sys from heapq import heappop,heappush input=sys.stdin.readline n=int(input()) q=[] for _ in range(n): x=int(input()) if ..
순서대로 n의 범위가 달라지고 수열의 길이만 구하는 것에서 실제 수열 요소를 구하는 순으로 어려워진다. 2번 문제는 1과 범위만 다르므로 dp로 풀 수 없고 이진탐색, bisect(python)으로 풀어야한다 2020/11/23 - [백준] - [11053번] 가장 긴 증가하는 부분 수열 (python, bisect) 2020/11/23 - [백준] - [백준 12738번] 가장 긴 증가하는 부분 수열 3 (python, bisect) 2020/11/24 - [백준] - [백준 14002번] 가장 긴 증가하는 부분 수열 4 (python, bisect, 어려움) 2020/11/25 - [백준] - [백준 14003번] 가장 긴 증가하는 부분 수열 5 (bisect, python)
www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 4번 문제와 똑같이 풀면 된다. 이번에는 q에 초기 숫자를 하나 넣어주는 대신 비어있거나 현재 원소가 q의 마지막 원소보다 크면 추가해주는 방식으로 했다. n의 범위만 달라지므로 초기값을 넣어줬었다면 이 부분만 주의하면 된다. temp 배열을 출력하면 이렇게 나오고 [(0, 10), (1, 20), (0, 10), (2, 30), (1, 20), (3, 50)] ans 배열에 넣을..
www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1,2,3 까지는 쉬웠는데 4부터 난이도 급상승 ㅠ O(n^2)으로 푼 사람이 많은데 n이 커진 문제인 경우 못풀걸 알아서 더 줄여서 풀고 싶었다 혼자서 시도해보다가 다른 사람 풀이 참고해서 풀었다. 아직 알고리즘 머리가 부족하군.. 이전 문제들에서 이전보다 더 작은 수가 등장했을 때 위치를 갱신하는 것은 익숙할 것이다. 여기서는..
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 부분 수열의 길이만 구하는 문제고 실제 어떤 원소가 부분 수열을 이루고 있는지나 해당 원소의 인덱스를 구하는 문제가 아니라서 쉽게 구할 수 있다. 심지어 이 문제는 O(N*2)을 해도 풀리기 때문에 (1초= 10^9를 넘어가지 않으면 된다) 이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되..
www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. python 풀이 from collections import deque import math from itertools import combinations chicken,house=[],[] n,m=map(int,input().split()) for y in range(n): temp=list(map(int,input().split())) for x in range(len(temp))..
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 2보다는 쉽다 더 짧게 갈 수 있는 경우 (check)를 더 작게 업데이트 해주자 from collections import deque N, K = map(int, input().split()) MAX_SIZE = 100001 q = deque() q.append(N) check=[-1]* MAX_SIZE check[N]=0 while q: x = q.popleft() i..