문제 : https://www.acmicpc.net/problem/6549 풀이 스택을 이용하여 풀었다. 기본적인 원리는 idx:0부터 순회하며 stack에 집어넣는다 만약, stack의 top의 height보다 클경우 push height보다 작거나 같을경우 아래의 과정을 거쳐 pop되고 push 진행 입력으로 "7 2 1 4 5 1 3 3"이 들어온다고 가정할 때, 들어오는대로 (idx,height)형태로 스택에 집어넣는다. idx :0일때, height=2는 스택이 비어있으므로 push ![](https://velog

문제 : https://www.acmicpc.net/problem/1197 풀이 최소 스패닝 트리를 이용해 푸는 문제이다. 크루스칼 알고리즘을 이용했다. 노드가 어떤 노드와 연결되어 있는지 정보를 담을 nodes 배열과, 어떤 노드가 연결되어 있고 가중치가 몇인지 담을 배열 li를 준비한다. 두가지 함수를 준비한다. find함수는 노드a가 연결되어 있는 루트노드를 찾아 리턴한다. union함수는 a와 b의 루트노드가 다를 경우, 연결하여 준다. li배열을 가중치 오름차순으로 정렬해 준다. li배열을 순회하면서 a와 b의 루트노드가 다를경우, 결과값가중치에 v를 더해주고, a와 b를 union 해준다. 마지막으로, 결과값가중치를 출력

문제 : https://www.acmicpc.net/problem/2636 풀이 공기와 접촉된 치즈는 매 턴마다 녹아 공기가 되는 문제이다. 이때, 중요한 점은 치즈로 둘러쌓인 공기 주변의 치즈는 녹지 않는다. 즉, 치즈를 녹일 수 있는 공기와 녹일 수 없는 공기를 별도로 분리하는게 핵심! 처음, 치즈를 녹일 수 있는 공기를 분리한다(배열에서 0->2로 변경) 그리고 본격적인 턴에 들어간다. bfs를 이용해 치즈를 녹일 수 있는 공기 주변 1칸에 있는 치즈들을 별도로 배열에 넣는다. 만약, 치즈를 녹일 수 있는 공기 주변에 치즈를 녹일 수 없는 공기가 있다면, 해당 공기를 0->2로 바꿔준다 이후, 녹을 예정인 치즈들을 공기(2)로 치환해준다. 이번턴에 몇개의 치즈가 녹았는지 계산해준다. 마지막으로, 몇번의 턴이 걸렸는지, 마지막 턴에 몇개의 치즈가 녹았는지 출력

문제 : https://www.acmicpc.net/problem/17299 풀이 오등큰수: 수열 li가 주어질 때, li[i]의 오등큰수는 j(i<j)이면서 li[i]보다 등장횟수가 많으면서 가장 작은 j를 뜻한다. 즉, 수열li에서 li[i]보다 오른쪽에 있으면서 li[i]보다 등장횟수가 큰 수열값을 찾는것이 관건이다. ex) li=[1,1,2,3,4,2,1] 일때, 등장횟수는 F(1)=3, F(2)=2, F(3)=1, F(4)=1 오등큰수는 NGF(0)=li[0]인 1보다 많이 등장한 값은 없으므로 -1 NGF(1)= 동일 NGF(2)= li[2]인 2보다 많이 등장한 값은 1밖에 없으므로 1 NGF(3)= li[3]인 3보다 많이 등장한 값은 1, 2인데 2가 오른편에 있으면서 가장 가까우므로 2 NGF(4)= li[4]인 4는 위의 NGF(3)과 동일, 2 NGF(5)= li[5]인 2보다 많이 등장한 값은 오른쪽에서 1밖에 없으므로 1 NGF(6)= li[

문제 : https://www.acmicpc.net/problem/1015 풀이 해석이 좀 복잡해 보일 수 있는 문제이다. 위의 예제 1번을 참고하여 풀어보면 A수열 A[0]=2, A[1]=3, A[2]=1 이 주어질 때, B[P[i]]=A[i]를 만족하는 P수열을 찾아야 한다. 먼저 B수열을 구하여 보면 B[P[0]] = A[0] -> B[1] = 2 B[P[1]] = A[1] -> B[2] = 3 B[P[2]] = A[2] -> B[0] = 1 즉, 1 2 0 이라는 답이 나오게 된다. 위 풀이를 해석하여 보면, A수열의 i번째가 몇번째로 작은 숫자인지 구하는 문제이다. 즉, 예제 1번의 배열에서 2는 2번째로 작고, 3은 3번째로 작고 1은 1번째로 작으므로 1 2 0 이다. 먼저 A수열(li)을 입력받고, 오름차순으로 정렬된 sort_li 수열을 따로 만들어 준다. 그리고, li 수열을 순회하면서 해당 숫자가 sort_li배열에서 몇번째 idx인지 구해 결과배열에

문제 : https://www.acmicpc.net/problem/1038 풀이 참고로 이문제는 1174번(줄어드는 수)와 99% 유사하다. 백트래킹 혹은 조합을 통해 0부터 1000000까지의 줄어드는 수 조합을 찾는다. 이때,최대 감소하는 수(9876543210)는 N이 1022번째일때의 경우이므로, 그 이상으로 N이 들어올 경우 -1출력 처리.

문제 : https://www.acmicpc.net/problem/1049 풀이 끊긴 기타줄 N개를 6개세트와 단품가격중 최소비용으로 채우는 문제이다. 주어지는 6개 세트가격과 단품가격을 각각 리스트에 담는다 이때, 6개 세트가격이 단품6개가격보다 크다면, 세트가격을 단품6개가격으로 변경 후 리스트에 담아준다. 그 후, 두 리스트를 정렬해주고 6개 세트중 가장 낮은가격으로 N을 최대한 채워 준 뒤, 남은 나머지x를 단품중 가장 낮은가격*x와 세트중 가장 낮은가격중 더 낮은값으로 처리해준다.

문제 : https://www.acmicpc.net/problem/13549 풀이 일반적인 bfs가 아닌 0-1를 이용하는 문제이다. 0-1 bfs는 아래과정과 같이 진행된다 deque의 front(left)에서 현재노드를 꺼냄 연결된 인접 노드 탐색 해당 인접노드를 탐색할 수 있을 경우(이동가능한 경우) 해당 노드를 향하는 가중치가 0이면 덱의 front(left)에 삽입 해당 노드를 향하는 가중치가 1이면 덱의 back에 삽입 가중치가 가장 낮은 정점으로의 이동을 우선순위로 해야하므로 덱의 front에 삽입하게 된다. 일반 bfs와 동일하게 간선의 갯수(E)만큼 탐색, 정점의 갯수(V)만큼 중복없이 방문하므로 시간복잡도는 O(V+E)로 동일하다.

문제 : https://www.acmicpc.net/problem/9935 풀이 stack을 이용해 해결하는 문제이다..! 처음엔 단순하게 폭탄문자열을 replace함수를 이용해 지워주는 방향으로 진행했는데 당연하게도 시간초과가 뜬다 _ex) aaaaaaaaaaaaa..... bbbbbbbbb ab 입력일 경우, 시간복잡도가 굉장해진다.._ 그러므로 시간복잡도를 줄이기 위해 stack을 이용한다. 문자열 S의 idx=0부터 stack에 쌓는다 만약, stack의 마지막 문자가 폭탄문자열의 마지막 문자와 같을경우 stack을 폭탄문자열 길이만큼 끝부분을 슬라이싱 한 결과가 폭탄문자열과 같을경우 그 길이만큼 stack에서 pop!

문제 : https://www.acmicpc.net/problem/4134 풀이 정수론을 이용해 해결하는 문제이다. 에라토스테네스의 체로 소수들을 미리 뽑아놓고 찾는방식으로 진행하려했지만 범위가 너무커서 시간초과가 떴다 ㅠㅠ 정수론에서 "임의의 양수 M이 합성수이면 √m 보다 작거나 같은 약수를 가진다." 라는 정리를 이용해 "임의의 양수 M이 √m 보다 작거나 같은 양수를 가지지 않으면 소수이다." 라는 결과를 이용한다 n이 0 또는 1일경우, 2 출력후 끝. n이 √m 보다 작거나 같은 약수를 가지지 않으면 n 출력후 끝. n이 √m 보다 작거나 같은 약수를 가지면 n+=1 후 2번으로 되돌아가기.

문제 : https://www.acmicpc.net/problem/2629 풀이 배낭문제(knapsack problem)를 응용한 문제이다.(12865번 문제 참고) 점화식을 아래처럼 설계한다. dpi=i번째 추를 넣을경우, 안넣을경우, 반대편에 넣을경우 만들 수 있는 구슬의무게 즉, i-1번째 무게가 weight이고 i번째 추의 무게가 j인 경우 dpi dpi dpi 위의 3가지는 구슬의 무게로 가능한 가짓 수 이다. 이때, weight-j는 0보다 커야하며(무게가 음수일 수는 없다) 중복되는경우는 없애는 것이 좋다(재귀함수 반복 줄이기) dp배열이 완성된 경우 해당 구슬의 무게에 해당하는 dp배열을 순회하면서 True가 있는지 조회. 아래의 방법은 2차원 dp배열 대신 set을 이용한 방법이다. 위와 같은 방법으로 이루어지지만, set을 이용해 훨씬 간결하게 작성된 방법.

문제 : https://www.acmicpc.net/problem/11066 풀이 dp를 이용해 해결하는 문제이다. 최소비용은 책이 n권있다고 가정할 때, 매번 합칠때마다 비용이 중첩되어 발생한다 즉, 1~n권까지의 각각의 책의 비용+매번 합칠때 드는 비용 = 최소비용이다. dpi=i에서 j까지의 최소비용으로 점화식을 계산한다. 최소비용의 계산방법은 아래와 같다 **편한 계산을 위해 idx는 1부터 시작하게 임의로 설정했습니다. 주어진 크기가 li=[0,40,30,30,50,20]인 예시로 확인해본다. 책을 합치는 구간이 1일때, 먼저, dpi=는 존재하지않는다.(합치지 않아 비용이 발생하지 않으므로) ![](https://velog.velcdn.com/images/www-jong/p

문제 : https://www.acmicpc.net/problem/14503 풀이 문제설명이 좀 복잡한 문제다. 주변 4칸중 청소되지 않은 빈칸이 있는 경우, a. 현재 바라보고 있는 방향에서 왼쪽으로 회전한다 b. 바라보는 앞칸이 청소되지 않고 벽이 아닌경우, 전진한다. c. 바라보는 앞칸이 청소되어있는 칸이거나 벽인경우, a로 돌아간다. 2.주변 4칸중 청소되지 않은 빈칸이 없는경우 현재 바라보는 방향에서 뒤로 1칸 이동이 가능한 경우, 후진한다. 아닐경우(뒤에 벽이있을경우), 청소기 작동중지! 먼저, 지도를 li배열에 담아주고, 똑같은크기의 배열 visit를 만들어준다(청소확인용) 그리고 왼쪽으로 돌아가면서 청소가 가능한 빈칸이 있는지 찾는다. 이때, 방향회전에 주의한다! 시게 반시계방향(북,서,남,동)으로 돌아야하므로 dx,dy의 idx=0,1,2,3 -> 북동남서 에서 idx-=1씩 진행되게 (d+3*i)%4의 계산으로 세팅했다.

문제: https://www.acmicpc.net/problem/12100 풀이 상하좌우 4가지로 이동할때의 함수를 만들고 dfs로 매번 상하좌우 전체의 경우를 구해본다. 그리고 5번째에 각 배열에서 최대의 값을 비교한다. 처음엔 단순무식하게 진행했다. 상하좌우 각 함수를 ex) 상(up)일 경우 idx=1(편의상 0말고 1부터 이동)이 0일경우, 아래의 칸들을 모두 위로 1칸씩 올린다. idx=1이 0이 아니고 idx=2의 값과 같을경우, idx=2의 값을 0으로 바꾸고 idx=1의 값을 *2한다 그리고 idx+=1 아래의 알고리즘의 문제점은 아래의 테스트케이스에서 나타났다(14%에서 틀렸습니다. 뜸). 5 2 2 4 8 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 4 8 16 -> up 진행시 4 4 8 16 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 위의 정답결과가 아니라 아래의 결과가 나온다 2 2 4

문제 : https://www.acmicpc.net/problem/18185 풀이 이게왜 다이아5..? 아는사람은 안다는 점수꿀빨기 문제이다. 기본적으로 3개구매 -> 2개구매 -> 1개구매가 가장 최소의 비용이 들지만 1 4 2 3 1 같은경우 1) idx=0에서 3개구매 -> 0 3 1 3 1 , 7원 2) idx=1에서 3개구매 -> 0 2 0 2 1 , 14원 3) idx=1에서 1개x2구매 -> 0 0 0 2 1 , 20원 4) idx=4에서 2개구매 -> 0 0 0 1 0 , 25원 5) dix=4에서 1개구매 -> 0 0 0 0 0 , 28원 1) idx=0에서 2개구매 -> 0 3 2 3 1 , 5원 2) idx=1에서 3개구매 -> 0 1 0 1 1 , 19원 3) idx=1에서 1개구매 -> 0 0 0 1 1 , 22원 4)

문제 https://www.acmicpc.net/problem/1991 풀이 이진트리를 입력받아 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)를 구현하는 문제이다. 처음에 트리의 입력이 노드순서대로 입력되는줄 알았는데 아니여서 개고생 ㅠㅠ 트리의 순서가 무작위로 입력되므로 이를 tree배열에 잘 넣어주어야 한다. t,l,r을 입력받는다 t를 인덱스로 변환시킨다(A -> ord(A)-64 -> 1번인덱스)(트리는 인덱스1시작이 편하드라..) tree, lefttree, righttree에 변환된 인덱스위치에 t, l, r값을 넣어준다. 모두 입력받았으면 전위, 중위, 후위순회 진행! 재귀함수로 진행한다. 전위순회 : root -> left -> right 중위순회 : left -> root -> right 후위순위 : left -> right -> root

문제 https://www.acmicpc.net/problem/6588 풀이 소수를 구하는 것이 핵심 에라토스테네스의 체를 이용해 100만이하의 소수를 구한다.(소수일경우 1, 아닐경우 0) 그리고 테스트케이스의 수를 고려해 input은 stdin.readline()를 이용! 테스트케이스 n를 입력받는다. 에라토스테네스를 통해 구해진 배열arr을 3부터 순회한다 3부터 순회하는 이유는 2는 짝수이기때문에!(두 홀수인 소수의 합을 찾아야함) arr[i]과 arr[n-i]이 소수일경우 정답을 출력하고 소수배열순회 종료 위 풀이는 python3 제출시, 시간초과이다. pypy3로 제출시, 688ms로 통과! 아래코드는 개선한 코드이다. 소수배열을 순회하지만, 소수가 아닌 숫자가 더 많아 소수만 따로 담는 배열과 딕셔너리를 이용해 순회시간단축! 아래코드를 통해 python3 제출시, 1912ms, pypy3 제출시, 340ms