본문 바로가기

알고리즘

 (368)
[Python] 1015번 수열 정렬 1015번: 수열 정렬 (acmicpc.net) 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 22/08/30 이 날은 피곤해서 한 문제밖에 못 풀었던 날이다. 그 문제는 1015번 수열 정렬. 이전에 한 번 잠깐 보고 무슨 말인지 몰라서 패스했던 문제였는데, 나중에 예제를 보니 무슨 말인지 알 것 같아서 바로 풀어보았다. 접근 방법: 주어진 원래 수열이 있다고 해보자. 이를 수열 1이라고 칭하자. 그리고 수열 1을 오름차순(비내림차순)으로 수열을 정렬했..
[Python] 13549번 숨바꼭질 3 (추후 보강 예정) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 22/08/29 이것도 숨바꼭질 문제를 풀고 난 후 풀었던 문제이다. 이 문제에 대한 정확한 해설은 아직도 잘 이해하지 못한 상황이므로, 추후 보강해서 작성할 예정이다. (쉽게 얘기하자면 맞았는데 아직도 정확하게 왜 맞았는지 증명을 하지 않은 상황) [Python] 1697번 숨바꼭질 (tistory.com) [Python] 1697번 숨바꼭질 https://ww..
[Python] 12851번 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 22/08/29 숨바꼭질 문제를 풀고 난 후 시리즈로 있길래 바로 풀어본 문제이다. 숨바꼭질 코드에서 약간의 수정만 거쳤으며, 기본 베이스가 되는 아이디어는 숨바꼭질 문제와 같다. https://lighter.tistory.com/15 [Python] 1697번 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수..
[Python] 1697번 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 22/08/29 이 문제는 BFS를 익히는 데에 있어서 정말 좋은 문제이다.(만약 BFS 알고리즘을 배우지 않았다면 당장 배우고 오는 것을 추천한다) 클래스 3에도 있던 문제이기도 했고, 이전부터 계속 풀어봐야지 풀어봐야지 하고 생각하고 있었는데 까먹었었다. 그러다가 최근에 "클래스에서 못 풀어본 문제를 풀어보자"라고 다짐해서 계속 클래스 문제들을 밀고 있다가 이 문제를..
[Python] 18111번 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 22/08/28 이 문제 또한 클래스 2++ 문제 중 풀지 않은 문제가 있길래 풀어본 문제이다. 처음에 문제를 접근할 때, 분명 브루트 포스 문제이긴 한데 주어진 제한시간이 생각보다 여유롭지 않아서 마음속으로 어떻게 문제를 풀지 고민을 많이 했었다. 그래서 한 번 정도 시행 착오를 겪고 나서 푼 문제이다. 참고로 python3로는 시간이 너무 빡빡한 탓에 pypy로 제출했으니, python3로 ..
[Python] 4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 22/08/28 마찬가지로 클래스 2++ 문제 중 안 푼 문제가 있길래 풀어본 문제이다. 전형적인 스택을 사용한 응용문제이며, 괄호 문자열에 대한 개념을 알고 있었으면 더 쉽게 푸는 문제이다. 접근 방법: 문제에서 주어진 대로 접근했다. 이제 괄호 스택을 하나 만드는데, '(' 나 '['가 나올 때마다 괄호 스택에 차곡차곡 그 괄호들을 넣어준다. 마찬가지로, ')' 나 ']'..
[Python] 2805번 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 22/08/28 보자마자 날먹 문제라고 생각했다. 이 문제는 그제 풀었던 1654번 랜선 자르기 문제와 거의 동일한 문제였기 때문이다. 단지 약간의 조건만 달랐다. 문제 접근 방법: 랜선 자르기 문제와 동일한데, 나무를 일정 간격으로 계속 자르는 게 아니라, 일정 높이를 두고 일정 높이 이상인 나무만 한 번 자른다는 점만 다르다. 다시 말해, 나누기를 하는게..
[Python] 1874번 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 22/08/28 마찬가지로 클래스 2++에 해당하는 문제 중 풀지 않은 문제가 있어서 풀은 문제이다. 문제 풀이 자체는 그렇게 마구 어렵다거나 그러지는 않는데 문제 해석이 조금 난감했던 문제이다.(내 국어 능력이 부족한 탓 일 수도 있다.) 하지만, 여러 번 틀렸다거나 그러지는 않았고 한 번에 맞았다. 지금 되돌아 ..

티스토리툴바