전체 글
[백준] 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약해보면, N*M의 0과 1로 표현된 array가 주어집니다. 이때 1은 벽을 의미하는데 (1,1)에서 (N,M)으로 이동할 때, 벽을 최대 1개까지 부수고 이동이 가능합니다. 이 때, 최단거리를 출력하는 문제입니다. 만약 최단거리가 없다면 -1을 출력해야합니다. 이 문제는 기존 bfs에서 주로 두는 visited a..
[백준] 내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍을 이용하여 푸는 문제입니다. 우선 문제부터 간단하게 요약하면, 1 2 3 4 5 6 7 8 9 9 7 1 위의 그림과 같이 array가 주어집니다. 이때, 가장 위에서 원룡이가 내려가게 되는데, 바로 아래방향에 있는 수로 넘어가거나, 그 수와 붙어있는 수로만 이동할 수 있다는 조건이 있습니다. 이때, 가장 아래까지 도달했을 때, 얻을 수 있는 최대 점수와 최소 점수를 return 해야 합니다..
[백준] 트리 순회
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*+ (중위표기식 -> 후위표기식) 옛날에 스택을 이용한 계산기 만들기를 해본 기억을 되살려 문제를 해결하였습니다. 우선 알고리즘은 다음..