Language/Python

10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이에 도움 되었던 블로그 😊 [알고리즘] Next Permutation NextPermutation 현 순열에서 사전 순(오름차순)으로 다음 순열을 생성합니다. 즉 배열을 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap하면서 출력합니다. 만약 숫자배열이라면 각각의 자리를 합해서 velog.io 문제 풀이 해당 문제는 permutation 알고리즘에 대해 알고 있으면 쉽게 문제를 해결할 수 있다. c++에서는 알고리즘 라이브러리에서 next_permutation을 제공하고 있고, python에서는 itertools에..

23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net 풀이과정 해당 문제를 해결하려고 많은 시행착오가 있었습니다. 😂 맞왜틀.. python3로는 해결할 수 없는 건가.. 실력이 부족하여 해결하지는 못했지만 혹시 해결하신 분 있으시면 댓글로 달아 주시면 감사하겠습니다. 😊 1. 해당 문제는 dfs, bfs 둘 다 사용하였다. 2. 데이터를 입력받을 때 "S"와 "K"의 좌표를 미리 dist 배열에 튜플 형식으로 입력받았다. 입력받을 때는 "S"에서 시작하기 때문에 dist 배열의 0번째 인덱스로 두었다. 나..

14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 풀이 과정 해당 문제는 세그먼트 트리를 알고 있어야 해결할 수 있습니다. 쿼리의 개수가 십만 개인데 배열의 크기마저 최대가 10^9입니다. 해당 문제를 단순하게 인덱스 사이의 min 값으로 출력하게끔 설정하면 0.1초 만에 시간 초과를 보게 될 것입니다. 😶‍🌫️ 그렇다면 세그먼트 트리가 무엇인가? 배열의 "연속적인" 구간 합 또는 구간의 min, max 값을 찾을 때 사용하는 알고리..

17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 해당 문제는 정말 주어진대로 문제를 풀었습니다. 똑같은 곧을 방문한 적이 있으면 출력 값을 1 더해주고 반환해주고, 개미 놈이 이동할 수 있는 경우를 다 설정하여 해당 방향에서 양 갈래 길로 가는 경우로 dfs 탐색을 해주었습니다.. 하지만 python으로는 이렇게 주어진 대로 문제를 해결하면 시간 초과가 발생하네요.. 경우의 수가 1부터 22까지이기 때문에 미해결 코드로 1부터 22까지 출력해서 밑에 코드로 제출했더니 통과가 되었네요.. print(..

23741번: 야바위 게임 첫 번째 줄에 정점 수 $N$, 간선 수 $M$, 게임 시작 시 공이 놓여있는 정점 번호 $X$, 공이 든 컵이 움직인 횟수 $Y$가 주어진다. ($1 \leq N, Y \leq 10^3$, $1 \leq M \leq 10^4$, $1 \leq X \leq N$) 다음 줄부터 $M$ www.acmicpc.net 풀이과정 멍청한 상원이.. 그거 하나 제대로 기억 못 해서 나를 이렇게 힘들게 하다니,, 🤦‍♂️🤦‍♂️ 해당 문제는 DFS로 접근하였습니다. 아마도 BFS로 접근하여도 무리 없이 문제를 해결할 거예요 시작 시 공이 놓여있는 정점 번호(x)부터 시작하여서 연결된 다른 정점으로 이동해서 이동 횟수가 Y인 정점을 저장해주면 됩니다. 하지만 해당 정점으로 이동할 때 정점으로 ..

19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 풀이 과정 만약 문제가 잘 이해 안 된다면 표를 잘 보시면 됩니다. 😊 표의 예시에서 "HI-ARC"가 root 노드로 시작됩니다. 그러기 때문에 root 노드 "HI-ARC"의 왼쪽 노드는 order을 1로 가집니다. 그 이후에 "HI-ARC"와 연결된 노드를 찾습니다. 표에서는 "경영 지원실"이 제일 빠른 노드입니다. 해당 "경영 지원실"의 왼쪽 노드는 다음 order인 2를 가집니다. "경영 지원실"과 연결된 노드... 노드... 연결된 ..

t or reversed_front > h : continue if t - reversed_back + reversed_front in visited : continue visited[t-reversed_back+reversed_front] = True q.append([t-reversed_back+reversed_front,depth+1]) else : print(-1)

16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net 풀이과정 해당 문제를 푸는데 거의 1시간 반을 써서 해결했다. 🤣🤣 그것도 아이디어가 생각나지 않아서 다른 분의 코드를 확인하면서 해결했다. 이 문제의 핵심은 "투 포인터"로 문제를 해결해야 한다. 1. 기준점 인덱스로부터 증가하는 팰린드롬의 길이를 구해야 한다. 2. 팰린드롬의 길이는 최소 1이 될 수도 있다. 3. start, end라는 배열의 인덱..