본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 9996번 한국이 그리울 땐 서버에 접속하지 https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 22/09/13 이 문제 또한 정규 표현식을 사용하여 풀 수 있는 문제로, 왜 실버 3인지 이해가 안 됐었다. 근데 알고 보니 정규 표현식 말고 쉬운 방법이 있었는데, 양 끝만 비교하면 되는 방식으로, 훨씬 간단했다. 문제 접근 방식: 나는 정규 표현식으로 접근했다. 그러려면 먼저 패턴을 만들어 주어야 한다. 문제에서 주어진 내용은 'a*d'인 경우 *사이에 아무..
[Python] 9342번 염색체 https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 22/09/13 정규 표현식을 사용하여 쉽게 풀은 문제로, 개인적으로 정규 표현식 자체가 어려운 내용이어서 골드 5부터 시작하는데, 이게 왜 실버 3에 위치해 있는지 의문인 문제였다. 문제 접근 방식: 정규 표현식을 사용하여 풀었다. 만약 정규 표현식에 대하여 잘 모른다면, 박응용 저자님의 점프 투 파이썬을 참고하면 도움이 많이 될 것이다. 문자열은 {A, B, C, D, E, F} 중 0개 ..
[Python] 21938번 영상처리 https://www.acmicpc.net/problem/21938 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 22/09/13 오랜만에 풀어보는 그래프 탐색 문제여서 조금 맞왜틀을 많이 했던 문제이다. 지금 다시 보니 실수했던 부분이 많이 보인다. 이 문제를 2가지 방법으로 풀려고 해봤으나, BFS는 익숙하지 않아서 BFS로 해결하지 않았다. 문제 접근 방식: DFS로 접근하였다. 오랜만에 DFS코드를 짜는 것이어서 많이 틀리기도 하고 시간 초과, 메모리..
[Python] 1927번 최소 힙 / 11279번 최대 힙 / 11286번 절댓값 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net https://www.acmicpc.net/pr..
[Python] 2491번 수열 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 22/09/12 이 문제 또한 그룹 채점 현황에서 있는 무작위의 문제를 골라서 푼 문제이다. 문제 접근 방식: 전형적인 DP문제인데, 나는 DP리스트를 2개로 세웠다. DP1은 가장 긴 감소하는 수열, DP2는 가장 긴 증가하는 수열의 DP리스트이다. 나는 DP1[i]를 i번째 원소까지 보았을 때, 가장 긴 감소하는 연속된 수열의 길이라고 정의했다. 일단 전부 1로 초기화를 하고, 반복문을 사용하여 ..
[Python] 1544번 사이클 단어 https://www.acmicpc.net/problem/1544 1544번: 사이클 단어 사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 www.acmicpc.net 22/09/11 그룹 제출 현황에 있는 문제를 아무 문제나 무작위로 한 문제 골라서 풀었다. 문제 접근 방식: 원형으로 쓴다는 아이디어에서 착안하여 덱 자료구조를 떠올렸다. 파이썬의 deque은 rotate라는 메서드가 존재하기 때문에 이 메서드를 활용하면 될 것이라고 생각했다. 구현은 다음과 같이 진행했다. 새로운 단어가 나오면 cycle_word라는 리스트에 그 새로운 단어를 원형으로 써서 읽힐..
[Python] 3709번 레이저빔은 어디로 https://www.acmicpc.net/problem/3709 3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net 22/09/10 그룹 연습에서 풀었던 문제로, 시뮬레이션 문제를 오랜만에 풀어보는 터라 당황스러웠지만 재미있기도 했다. 문제 접근 방식: 특별한 알고리즘은 없고, 문제를 말 그대로 구현했다. 근데 보드를 딱 N*N크기로 구현한 것이 아니라, 그보다 위아래 왼쪽 오른쪽으로 1칸씩 크게 만들었다. 그 이유는 보드에서 레이저를 쏜다고 했으니, 그 레이저를 놓을 공간이 필요하다고 생각했기 때문이다. 우향..
[Python] 14607번 피자 (Large) https://www.acmicpc.net/problem/14607 14607번: 피자 (Large) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 22/09/10 마찬가지로 그룹 연습에서 풀었던 문제이다. 규칙을 찾아서 풀었으며, 굉장히 쉬웠다. 문제 접근 방식: 문제 풀 땐 그냥 나열해서 규칙 찾아서 풀었다. 그 식은 바로 $\frac{n(n-1)}{2}$였다. 근데 정당화를 해봐야 했었다. 결론만 이야기 하자면 어떻게 피자판을 쪼개든 항상 값은 같게 나온다. 예를 들어, $n$인 피자판을 $k$와 $n-k$로 쪼갠다고 해보자..

티스토리툴바