알고리즘-문제

문제문제보기어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.((2)) 같은경우 바깥괄호제거할 때랑 안쪽 괄호제거한 결과가 겹친다.set을 써서 제거해버리자. 코드

문제 보기다음과 같은 그래프가 주어졌을 때 1번 노드에서 최단거리로 갔을 때 가장 멀리 떨어진 노드를 구하는 문제이다.본인은 dijkstra 알고리즘을 써서 각 노드 까지의 거리를 구하여 풀었다.모든 노드 사이의 거리가 일정하므로 bfs를 써도 풀 수 있다. dijks

문제문제 보기얻은 것처음에는 삭제할 때 마다 문자열의 처음으로 돌아가 다시 탐색하게 구현했는데 이러면 쓸데없이 계속 앞부분을 탐색해야 한다.stack에다가 문자를 계속 쌓으면서 진행하면 현재까지 진행 정보를 계속 가져갈 수 있어서 쓸데 없는 시간소요를 줄일 수 있다.

문제문제 보기 난 더럽게 풀었는데 다른사람 풀이랑 종회형 풀이 보니까 깔끔 하게 풀린다 종회형 풀이 13 = 111, 14 = 112, 15 = 114 이다. 뭔가 3진법이랑 비슷할테니까 나누기로 접근하자. 마지막자리는 일단 3으로 나눈 나머지이다.

문제문제 보기장욱이가 스터디에서 어렵다고한 문제이다.1,2,1,2,1,2,1,1,1,1,2,2,2,2,2 같은 수열에서 k개의 홀수를 제거할때 짝수가 가장 많이 연속되게 하는 경우 연속된 짝수의 수를 구하는 문젠데 '제거하는 홀수는 모두 정답에 들어가는 짝수와 붙어있다

문제문제보기풀이주목해서 봐야할 부분은 이 부분이다. 주어진 알파벳을 선택안하거나 선택하는 경우를 각각 재귀함수를 호출해서 실행하고 두 재귀함수가 끝난후에는 해당 알파벳을 선택하기 전으로 되돌려 놓은다음 함수를 끝낸다.

문제문제보기풀이nQueen 문제의 핵심은 체스판을 이차원 배열로 모두 저장할 필요가 없다는 것이었다.각 row마다 queen은 한개만 존재할 수 있으므로row = \[] 에다가 row를 차례대로 탐색하면서 퀸의 x좌표를 하나씩append하고 row의 길이가 n이되면 정

문제보기풀이주목해서 볼 부분은 다음이다.visited\[] 는 방문한 칸을 다시 방문하지 않기 위함이고 now_str{}은 이미 지나온 알파벳을다시 지나가지 않기 위해서 설정해 주었다.동서남북 방향으로 재귀함수를 통해 진행한다.x,y 가 범위를 넘어가거나, 해당 칸이

문제문제보기서로 높이가 다른 탑의 꼭대기에서 왼쪽으로 레이저를 쏠 때 레이저는 탑에 부딪히면 멈춘다. 각 레이저가 멈추는 위치를 구하라는 문제이다.출처:https://mygumi.tistory.com/101풀이아 이거 좀 생각해봤으면 좋았을 텐데 걍 답을 봤다

문제문제보기일직선위에 원이 여러개 주어지는데 만나는 원이 있는지 알아보라.풀이x-r, x+r 두 포인트를 주목하자. 같은 원의 두 포인트를 각각 여는 괄호, 닫는 괄호 라고 생각하면 쉽게 풀린다.(x-r, 여는괄호, 원번호)(x+r, 닫는괄호, 원번호)이렇게 리스트에

문제2022-03-25문제보기수식이 주어졌을때 해당 수식을 다음과 같이 후위표기식으로 바꾸는 문제이다.풀이노가다성으로 풀긴했는데 그다지 좋은 방법이 아니었다. 괄호때문에 아주 코드가 복잡해진다.종회형 말처럼 일단 몇가지 예시를 스스로 끄적여 보면서 아이디어를 떠올려보자

문제문제보기n by n 표에 n^2개의 수가 채워져있다. 규칙은 각 column이 오름차순으로 되어있다는 것이다.각 column에 진행중인 index를 가르키는 pointer 를 둔다. 그 열에서 가장 큰 수가 나오면 index를 -1 해주고 이 과정을 n 번 반복한다

문제2022-03-27문제 보기위의 자료에서 처럼 큐에 주어진 숫자를 넣고 명령에 따라 자유롭게 max, min을 pop해야 한다.효율적으로 알고리즘을 짜야하는 문제이다.max_heap min_heap을 구현하는 것 까지는 했는데 max_heap에서 popleft()

문제2022-04-29문제 보기배열이 있고 배열을 index 순으로 탐색하는데 홀수번 index마다 0~index 까지의중앙값을 print 하라는 문제이다.풀이나는 새 배열을 만들어서 숫자를 넣을때마다 이분탐색으로 숫자를 넣었다. 그래서 insert 모듈을 쓰므로 O(

문제2022-03-29문제 보기이런 식으로 각 트리의 data,left,right이 주어지면 root를 A로 지정한 다음 트리를 만들라는 문제풀이class를 재귀적으로 선언해서 tree를 만듦. init(self,data,list)로 초기화.data는 해당 tree의

문제2022-03-29문제보기이런식으로 tree랑 지울 노드가 주어진다.첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이

문제2022-03-29문제 보기inorder 방식으로 순회한 결과가 주어질 때 tree를 만드는 문제이다.풀이결과의 가운데 부분이 tree의 root이므로 이 과정을 반복하면 된다.

문제2022-03-31위와 같은 그래프가 주어졌을 때 해당 그래프가 트리인지 판별하는 문제입력은 다음과 같이 주어진다.

문제2022-03-31문제 보기트리를 전위 탐색한 결과가 input으로 주어진다. 왼쪽 트리는 루트보다작고 오른쪽 트리는 루트보다 큰 이진트리이다.풀이카카오 트리문제처럼 class를 써서 root보다 작은애들은 left로 넘기고 root보다 큰애들은right로 넘겨서

문제2022-05-05문제 보기두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.풀이짧은 문자열 S 로부터 경

문제 보기

문제문제 보기얻은 개념ord() 를 사용하여 알파벳을 index로 매치하여 풀었다.ord('Z')와 ord('a') 사이에 다른거 6개 있다.주의하자 ㅜㅜㅜ

문제문제 보기다음 그림과 같이 board 가 주어진다. 물웅덩이는 지나갈 수 없다.집에서 학교까지 아래, 오른쪽으로만 움직여서 갈 수 있는 최단경로의 개수를 구하는 문제이다.풀이for문을 두 개돌려서 모든 칸을 순서대로 탐색하고 각 칸에는그 칸까지 가는 경로가 저장된다

문제 보기각 칸에는 해당 위치의 높이가 적혀져 있다.높이가 낮은 칸으로만 움직일 수 있다.0,0에서 출발하여 맨 오른쪽 맨 아래칸까지 가는 경로의 수를 구하시오.풀이종회형이 던져준 dfs memoization에 대해 공부하다 풀게된 예제이다.dp로 어떻게 푼다는 말인지

문제 문제 보기다음과 같이 점수가 부여된 스티커가 있다.양옆, 위아래로 인접한 스티커를 동시에 선택할 수 없다.스티커를 선택하여 획득할 수 있는 가장 큰 점수를 구하시오.풀이우선 나는 1차원 dp로 풀고자 했다. 아이디어는 이렇다.각 dp마다 그 칸까지 진행했을 때

문제 보기다음 표에서 T는 상담에 걸리는 시간(일)이고 P는 상담으로 버는 돈이다. 마지막날까지 하고 퇴사한다고 할 때 가장 많이 벌 수 있는 돈을 구하시오. 단 ,일은 0시 부터 시작한다. 즉, 마지막날 1짜리 일은 할 수 있는 것이다.풀이처음에는 dfs memoiz

문제문제 보기요약하면 양이 다른 포도주잔이 쭉 놓여 있다. 세 잔 연속해서 마시는 것이 불가능 할 때 마실 수 있는 최대한의 포도주양을 구하라는 문제이다.풀이아이디어만 떠올리면 쉽게 풀리는 문제였다. 예전에 dp를 처음 배울 때 '타일 설치'문제를 기억하라. 문제는 좀

문제문제 보기다음과 같은 상자안에 토마토를 보관한다. 익은 토마토, 안익은 토마토, 빈 칸 세 종류가 있다. 안익은 토마토가 익은 토마토옆에 하루있으면 익는다. 모든 토마토가 익는데 걸리는 시간을 구하시오.풀이각 익은 토마토에서 안익은 토마토로 bfs를 진행하면 쉽게

문제 보기한 번에 듣는 과목수에 제한이 없을 때 모든 과목을 듣는데 몇학기가 걸리는지 구하시오. 풀이 defaultdict(set)을 사용하여 각 dict에 선수과목을 set형태로 적어넣고 deque로 현재 들을 수 있는 강의를 설정한 다음 while문을 돌면서 deq

문제문제 보기두 명씩 키를 비교한 결과만 m개 주어질 때 전체 학생을 키 순서로 정렬하라는 문제이고 답이 여러개일 때 그 중에서 아무거나 출력하라는 문제이다.풀이출처: https://m.blog.naver.com/ndb796/221236874984위의 방식으로

문제문제 보기0부터 N까지의 정수가 각각이 집합 하나를 이루고 있을때 주어진 명령어에 따라 집합을 합친다. 그 사이사이에 정수 A,B가 같은 집합에 속해있는지 묻는다.풀이find-union 알고리즘을 새로 배웠다.parent-child 관계를 통해 같은 root를 갖으

문제 문제 보기 다음과 같이 그래프의 간선들이 주어질 때 최소 스패닝 트리의 weight를 구하시오. a,b,c 로 주어질 때 a,b를 잇는 간선의 weight는 c라는 뜻이다. > 얻은 개념 문제는 어렵지 않게 풀었는데 Kruskal과 Prim's 알고리즘을

문제문제 보기논에 물을 대는 방법은 두 가지가 있다. 우물을 파거나 다른 논에서 물을 끌어오거나. 모든 논에서 다른 논으로 물을 끌어올 수 있고 모든 논에서 우물을 팔 수 있을 때 모든 논에 물을 대는 최소비용을 구하시오.풀이아이디어 하나만 있으면 쉬운 문제가 된다.

문제문제 보기동전의 종류가 주어진다. 동전은 1~10000 사이의 값을 갖는다. 숫자 M이 주어질 때 동전으로 M을 만들 수 있는 경우의 수를 구하여라.풀이DP는 그냥 여러 유형을 익히는 수 밖에 없는 것 같다. 풀이를 보고 풀었다.출처dp table을 1~M 까지 만

문제문제 보기LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.풀이아 dp 왤케