기록

[Programmers] 경주로 건설 [ python, bfs ]

코딩테스트 연습 - 경주로 건설 | 프로그래머스 (programmers.co.kr) def solution(board): answer = 0 # 아래 방향으로 시작하는 경우 down_x_dir = [-1, 1, 0, 0] down_y_dir = [0, 0, -1, 1] queue = [] # 시작 x, 시작 y, 방향, 가격 queue.append((0, 0, 1, 0)) # x,y에 도착했을 때 turn해서 왔는지는 따로 저장 price = [[[1e9 for _ in range(2)] for _ in range(len(board[0]))] for _ in range(len(board))] price[0][0][0] = 0 price[0][0][1] = 0 while queue: x, y, d, v =..

[BOJ] 1967 트리의 지름 - 그래프 이론, 다익스트라

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394041424344'''BOJ - 1967 트리의 지름 - 그래프 이론, 다익스트라 그래프와는 조금 색다른 트리의 지름이다. 기본 로직은 그래프의 지름과 같다. 똑같이 다익스트라를 이용하여 계산해주면 되는데 이 문제가 더 쉬운게 루트노드부터 입력하므로 항상 1번 노드가 ..

[BOJ] 1918 후위표기식 - 문자열, 스택

www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960'''BOJ - 후위 계산식 - 문자열, Stack = 연산자의 우선순위를 나눈 뒤, 일반 항은 바로 Answer에 추가시키고, 괄호나 연산자가 오면 스택에서 우선순위에 따라 처리한다.'''import sy..

[BOJ] 2668 단지번호붙이기 - dfs, graph

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 이번 프로그래머스 winter coding 3번 문제와 매우 흡사한 문제이다. union find를 해야 풀리는 문제인지 알았는데, 그래프가 아닌 이차원 배열 같은 경우 이를 구현하기가 상당히 까다롭다. 그리고 이런 구역 나누기 문제는 간단한 dfs로 해결 가능하다. 맵의 처음부터 끝까지 차례대로 순회하여 같은 구역일 경우 dfs를 계속 진행하고, 다른 구역인 경우 그 구역의 value로 또 dfs를 진행하며 vi..

[BOJ] 1786 찾기 - kmp알고리즘

www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net bowbowbow.tistory.com/6 kmp 알고리즘에 대해서는 위의 블로그에 설명이 아주 잘 되어있다. KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했 bowbowbow.tistory.com 1234567891011121314..

[BOJ] 1629 곱셈 - 분할정복

www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 일반적인 방식으로는 시간초과가 나는 문제이다. 따라서 분할정복을 통해 최대한 잉여계산을 줄인다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys def divide_conquer(a, b): if b == 1: return a % C else: tmp = divide_conquer(a, b//2) if b % 2 == 0: return tmp * tmp % C else: return tmp * tmp * a % C A, B, C =..

[BOJ] 12016 가장 긴 증가하는 부분수열 - 이분탐색

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 알고리즘 생각을 깊게 해야한다. 구하는 것은 가장 긴 부분수열의 길이이므로 문자열 자체를 구할 필요가 없다. 리스트를 순회하면서 현재 최대값보다 크다면 삽입하여 최대값을 갱신하고, 만약 현재 최대값보다 작다면 현재 리스트에서 알맞은 자리를 찾아 교체한다. 문자열 자체는 중요하지 않기에 가능한 방법이다. 만약 정답 문자열을 구해야 한다면, 교체 당한 숫자를 저장해둬서 처리해야 한다. 1 2 3 4 5 6 7 8 ..

[BOJ] 9251 LCS - DP, 문자열

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 먼저 두 문자열을 입력받는다. 개행문자 제거를 위해 strip()함수를 사용한다. 두 문자열의 길이만큼 이차원 배열을 만든다. dp[i][j]를 첫번째 문자열의 i번쨰까지의 부분문자열과 두번째 문자열의 j번째까지의 부분문자열 중 가장 긴 공통부분문자열의 길이로 정의하자. 두 문자열을 하나씩 늘려가면서 부분문자열을 비교해본다. 만약 첫번쨰 문자열의 [i]와 두번째 문자..