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/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 ..
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/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1과 다른 점은 배열 원소의 최소값이 -10^9이기 때문이다. 따라서 q의 처음 최소값을 그 수보다 작은 수로 하면 된다 import sys from bisect import bisect_left n=int(sys.stdin.readline()) arr=list(map(int,sys.stdin.readline().split())) #마지막 길이 출력 때 1을 빼준다 q=[-1000..
합한 수가 target이면 현재 수 x와 target-x의 위치를 찾으면 된다 각 숫자의 위치를 저장해가면서 이미 지나간 위치에서 target-x가 있다면 [현재위치, dict[target-x]] 를 리턴하면 된다. 1. python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict={} for i,x in enumerate(nums): if target-x in dict: return [dict[target-x],i] dict[x]=i 2. javascript /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var t..
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를 넘어가지 않으면 된다) 이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되..
파이썬 알고리즘 인터뷰 책을 기반으로 공부했는데 (다른 알고리즘 시험에서 안나올 것 같은 뒷 부분이나 중간에 링크드 리스트 부분은 좀 넘겼다) 까먹은 부분 복습할 겸 처음부터 다시 풀어보았다 요즘 사이드 프로젝트 때문에 리액트만 하고 있어서 자꾸 알고리즘을 푸는 감각을 잃는 것 같다 다시 건들어보려고 한다 125번. 펠림드롬 - 한 번에 성공 leetcode.com/problems/valid-palindrome/submissions/ from collections import deque class Solution: def isPalindrome(self, s: str) -> bool: s=[c.lower() for c in s if c.isalnum()] return s==s[::-1] 344번. 문자열..
숫자를 문자열로 변환해서 뒤집은 다음 연산한다 class Solution: def reverse(self, x: int) -> int: x=str(x) x=x[::-1] if x[-1]=='-': x=int('-'+x[:-1]) x=int(x) if x>2**31-1 or x