dmscks3126 님의 블로그

📍  문제 요약문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.예를 들어“3+4+5+6+7”  라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다."34+5+6+7+" 변환된 식을 계산하면 25를 얻을 수 있다.문자열 계산식을 구성하는 연산자는 + 하나뿐이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다. 🧩 로직 설계 1 >> 해답# 중위 표기식으로 주어지는 인풋을 후위표기식으로 바꾸는 방법# 숫자 (피연산자)는 출렦하꼬# 연산자 > 스택에 넣기# 스택의 마지막 요소보다 현재 연산자가 우선순위가 높으면 넣고# 그렇지 않으면 스택이 비거나, 혹은 스택의 마지막 요소가 우선순위가 낮을 때까지 출력 후 스택에 삽입 💡 소스 코드# 중위..

계산기의 의미계산기 1 : 계산기 2 :  계산기 1더보기문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.문자열 수식 계산의 일반적 방법step1. 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용) > 중위 표기법 (infix notation)- 연산자를 피연산자의 가운데 표기하는 방법ex) A+B > 후위 표기법(posftix notation)- 연산자를 피연산자 뒤에 표기하는 방법 ex) AB+ step2. 후위 표기법의 수식을 스택을 이용하여 계산한다. step1. 중위표기식의 후위표기식 변환 방법 1더보기수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다.괄호를 제거한다.e..

📍  문제 요약그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라. - A와 B는 숫자 0과 99으로 고정된다. - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다. - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다. - 단 화살표 방향을 거슬러 돌아갈 수는 없다.   💡 소스 코드# 0번 정점에서 시작해서 99번에 도착할 수 있으면, 1 아니면..

📍  문제 요약V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때,특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오.두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다. 노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다. 🧩 로직 설계 1 >> 해답1) stack에 현재 경로를 저장한다.2) visited 리스트로 이미 방문한 노드를 체크한다.3) 반복문 안에서 현재 위치 (top) 에서 연결된 노드들을 확인한다.4) 방문하지 않은 노드를 발견하면 그곳으로 이동한다. (스택에 추가)5) 더 이..

📍  문제 요약크기가 N인 파스칼의 삼각형을 만들어야 한다.파스칼의 삼각형이란 아래와 같은 규칙을 따른다.1. 첫 번째 줄은 항상 숫자 1이다.2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.N이 4일 경우,N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.  🧩 로직 설계 1 >> 해답1) 삼각형의 첫 번째 줄은 항상 1이다.2) 두 번째 줄부터는 각 숫자가 윗줄의 두 숫자를 더한 값이다.3) 프로그램은 한 줄씩 숫자를 채운 후, 다음 줄로 넘어가면서 같은 과정을 반복한다.4) 가장 중요한 점은 각 줄의 첫 번째 숫자와 마지막 숫자는 항상 1이고, 나머지 숫자는 이전 줄에서 두 숫자를 더한 값이다. 🎯 단계별 소스 코드 및 구현함수 정의..

DFS (깊이 우선탐색)더보기비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함.두 가지 방법깊이 우선 탐색너비 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여결국 모든 정점을 방문하는 순회방법가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 (수도코드)더보기visited[], stack[] 초기화DFS(v) 시작점 v 방문; visited[v]  DFS 예더보기초기상태 : 배열 visited를 False로 초..

DP더보기동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.  피보나치 수 DP 적용더보기피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다. 1) 문제를 부분 문제로 분할한다.Fibonacci(n) 함수는 Fibonacci(n-1)과 Fibonacci(n-2)의 합Fibonacci(n-1)은 Fibonacci(n-2)와 Fibonacci(n-3)의 합Fibonacci(2)는 Fibonacc..

재귀호출더보기필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성재귀 호출의 예) factorial n에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산더보기n! = n x (n-1)! (n-1)! = (n-1) x (n-2)! (n-2)! = (n-2) x (n-3)!... 2! = 2 x 1! 1! = 1 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복 factorial 함수에서 n=4 인 경우의 실행 피보나치 수열더보기0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 ..

📍  문제 요약 주어진 입력에서 괄호 {}, ()가 제대로 짝을 이뤘는지 검사하는 프로그램을 만드시오.예를 들어 {( )}는 제대로 된 짝이지만, {( })는 제대로 된 짝이 아니다.입력은 한 줄의 파이썬 코드일수도 있고, 괄호만 주어질 수도 있다. 정상적으로 짝을 이룬 경우 1, 그렇지 않으면 0을 출력한다. print(‘{‘) 같은 경우는 입력으로 주어지지 않으므로 고려하지 않아도 된다.  🧩 로직 설계 1 >> X1) 주어진 문자열을 stack에 하나씩 넣으며 검사2) '(' 라면 넣는다3) ')' 라면 '(' == stack[-1]  을 뺀다.4) 스택에 뭐라도 남았다면 괄호검사 실패 >> return 05) 안남았다면 괄호검사 성공 >> return 1 🧩 로직 설계 2 >> O1) 주어진..

📍  문제 요약문자열 s에서 반복된 문자를 지우려고 한다. 지워진 부분은 다시 앞뒤를 연결하는데,만약 연결에 의해 또 반복문자가 생기면 이부분을 다시 지운다.반복문자를 지운 후 남은 문자열의 길이를 출력 하시오. 남은 문자열이 없으면 0을 출력한다. 🧩 로직 설계 1 >> X1) 문자열 s를 스택에 1개씩 넣으면서 확인2) 스택에 넣을 때 TOP이 지금 넣을 것과 같다면, TOP을 pop하고 넣을 것도 넣지 않음3) 다음 것도 반복 ==> 반복 문자가 다 지워짐4) 스택에 남아 있는 요소의 길이 출력 🧩 로직 설계 2 >> O1) 문자열 s를 스택에 1개씩 넣으면서 확인2) 스택이 비어있으면 현재 요소에 스택 더하기3) 비어있지 않다면 스택의 마지막 요소와 현재 넣을 요소를 비교4) 같다면 마지막 ..