코딩테스트/Python 문제풀이
[백준] 트리 순회
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리 자료구조를 구현하고, 알맞게 순회할수 있게 해야하는 문제입니다. 우선 문제부터 간단하게 요약하면, Tree의 정보가 들어오면, 이 Tree의 Preorder, Inorder, Postorder traversal 결과를 알맞게 return해야 합니다. Node라는 class를 만들어서 이 자료구조를 관리해주는 형태로 진행하면 됩니다. class node: def __init__(se..
[백준] 트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net dfs를 사용하는 문제입니다. 이전에 해결했던 https://life318.tistory.com/58 [백준] 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가. li..
[백준] 정수 삼각형
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp를 이용하는 문제입니다. 이전에는 아래에서 위로 올라가는 다른 방식으로 풀이를 하였는데 dp로도 한번 다시 풀어보았습니다. https://life318.tistory.com/26 [프로그래머스] 정수 삼각형 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers...
[백준] 후위 표기식
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 스택을 이용하는 문제입니다. 우선 문제를 간단하게 요약하면, 컴퓨터에서는 후위 표기식을 사용합니다. 하지만 사람들은 식을 중위 표기식으로 나타냅니다. 이때, 중위 표기식을 후위 표기식으로 올바르게 고치는 코드를 작성해야 하는 문제입니다. a+b*c -> abc*+ (중위표기식 -> 후위표기식) 옛날에 스택을 이용한 계산기 만들기를 해본 기억을 되살려 문제를 해결하였습니다. 우선 알고리즘은 다음..
[백준] 공통 부분 문자열
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net lcs, lcp 문제로 흔히 불리우는 문제의 장르입니다. (dp로 해결) (이 문제는 longest substring 문제로 잘 알려져있습니다.) 우선 문제부터 간단하게 요약하면, 두 string이 input으로 들어오면, 해당하는 두 string의 부분 string중 가장 길이가 긴 것의 문자열 길이를 return 해야합니다. 간단한 그림을 통해 아이디어를 살펴봅시다. dp array..
[백준] 문자열 폭발
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 스택(stack)을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 문자열이 있고, 폭탄이 주어집니다. 문자열중 폭탄에 해당하는 문자열이 있는 경우 사라집니다. 이렇게 사라진 문자열에서 또 다시 폭탄에 해당하는 문자열이 있으면 또 사라집니다. 이 과정을 반복해 남는 문자열을 만드는 문제입니다. python에서는 문자열의 find 메소드를 제공합니다. 가장 처음에는 이 방법을 ..
[백준] N과 M (2)
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net itertools 라이브러리의 combination을 이용해서 해결하는 문제입니다. 우선 문제부터 간단하게 요약하면, N과 M이 주어지면, 1~N의 숫자중 중복없이 M개를 고른 수열을 사전순으로 출력해야 하는 문제입니다. itertools의 combination의 경우 combination을 어떻게 구성하는지 출력해보면 다음과 같이 사전순으로 출력하는 것을 알 수 있습니다. 따라서 sorted된..