본문 바로가기

분류 전체보기

 (341)
[백준 / BOJ] 5639 이진 검색 트리 문제 출처 : www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리를 전위 순회한 결과가 주어졌을때, 트리를 후위순회한 결과를 출력하는문제다. 풀이 문제는 간단한데 입력은 그렇지 않았다.. 처음에는 완전이진트리를 생각하고 구현하다가 런타임에러가 떴다(배열 범위 초과). 다시 잘 읽어보니 노드가 한쪽으로 쭉 늘어날수있었다. 완전이진트리로 구현할려면, 배열의 범위가 2^10000 까지 가야해서 이 방법으로는 풀수없다. 런타임에러 코드 더보기 런타임에..
[백준 / BOJ] 16953 A -> B 문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 정수 A와 B가 주어진다. A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다. 이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다. 풀이 전형적인 BFS문제다. BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다. A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다. 예시로, 1. *2 연산은 32번만 반..
[백준 / BOJ] 1918 후위 표기식 문제 출처 : www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 중위 표기법으로 입력된 수식을 후위표기법으로 바꾸는문제다. 후위표기법이란, 연산자가 피연산자 뒤에 위치하는 표기법이다. 후위 표기법의 예는 A+B = AB+ A+B*C = ABC*+ A*B+C = AB*C+ A*(B+C) = ABC+* 등이 있다. 풀이 구현문제다... 재귀로 풀었다. 처음에는 연산자를 피연산마 맨뒤에 쌓아놓기만 하면 되는거로 구현했다가 다 지우고 다시짰었다... 문제에서..
[백준 / BOJ] 1967 트리의 지름 문제 출처 : www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가중치를 가진 트리가 주어진다. 이때, 트리의 지름을 구하는 문제이다. 트리의 지름은 트리의 모든 경로들중 가장 긴 경로를 말한다. (가장 긴 경로를 지름으로 하는 원을 그리면, 모든 노드들을 해당 경로안에 집어넣을수있다.) 풀이 전형적인 트리의 지름을 구하는 문제다. BFS,DFS,다익스트라 등으로 풀수있는데, 최단시간으로 답을 구하는 방법은 다익스트라라고 생각해서 다익스트라..
[백준 / BOJ] 1991 트리 순회 문제 출처 : www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리가 주어졌을때, 해당 트리를 전위순회, 중위순회, 후위순회한 결과를 출력하는 문제다. 풀이 트리 탐방자체는 어렵지않았는데, 입력을 트리구조로만드는게 난해한 문제였다. (순회 문제를 푼게 아니라 트리구조를 만드는 문제를 푼느낌...) 기본적인 트리구조(idx*2, idx*2+1)에 익숙해져서인지 처음엔 그런방향으로 구현하는걸 생각했었다. 입력이 위에서부터 너비우선탐색으로 입력되는것 같아서 ..
[백준 / BOJ] 11053 가장 긴 증가하는 부분 수열 문제 출처 : www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열 A가 주어진다. 이때, 수열A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. 예를들어, 수열 : {1 2 1 4 5} 가 주어지면, 1 -> 2 -> 4 -> 5 가 가장 긴 증가하는 부분수열이되어서 답은 4이다. 풀이 수열의 길이가 최대 1000이므로 모든경우를 보면 시간초과가 난다. 하나의 수를 지정..
[백준 / BOJ] 11404 플로이드 문제 출처 : www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net n개의 도시와 m개의 도시를 연결하는 버스의 수가 주어진다. 버스를 타고 이동하는데 일정한 비용이 든다고할때, a도시에서 b도시까지 가는 최소 비용을 구하는 문제다. 풀이 이름에서 알수있듯이 플로이드 와샬 문제다. 기본적인 플로이드 와샬문제라서 그냥 플로이드 와샬을 쓰면 풀린다. 한 도시에서 중간도시를 거쳐 다른 도시로 가는 경우가있을수있기때문에, 중간도시를 거쳐가는 경우까지 봐주면된다. 도시의 ..
[백준 / BOJ] 11660 구간 합 구하기 5 문제 출처 : www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net N과 M이 주어지고, N*N그리드에 숫자들이 주어진다. M개의 범위가 주어졌을때, 해당 범위에있는 숫자들의 합을 구하는문제다. 예를들어, 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 그리드에서, 1 1 1 4 는 10이다. 풀이 (구간합 구하기 3을 풀다 도망쳤다...) 일반적인 완전탐색으로는 풀지못한다. N의 범위가 1024이고, M이 10..

티스토리툴바