본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 15650번 N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/06/25 옛날에 풀었던 문제를 오늘(22/12/01) 백트래킹으로 다시 풀어보았다. 이전에는 파이썬의 itertools묘듈의 combinations를 사용해서 문제를 해결했지만, 백트래킹을 연습하는 문제로, 백트래킹으로 풀어보기로 했다. 문제 접근 방식: 첫 번째 접근 방법은 N과 M (1)의 코드를 변형한 코드이다. 2022.12.01 - [백준 문제 풀이] - [Python] 1564..
[Python] 15649번 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/11/30 백트래킹의 기초적인 문제로, 단계별로 풀어보기에서 풀어볼 수 있다. 문제 접근 방식: 백트래킹은 주로 재귀+가지치기로 접근이 되어진다. 말 그대로 Backtrack이기 때문에, 쭉 갔다가 다시 돌아오는 작업이 필요하다. 때문에 깊이 있게 들어가는 dfs탐색으로 대부분의 문제가 풀린다. dfs는 스택을 이용할 수도 있고, 재귀를 이용할 수도 있지만, 일반적으로 재귀를 이용한 구현이..
[Python] 11478번 서로 다른 부분 문자열의 개수 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 22/11/30 단계별로 풀어보기에서 풀은 문제로, 부분 문자열을 찾아내는 방법과 집합 자료구조에 대한 사용법만 알고 있다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 모든 부분 문자열을 찾아내고, 이를 부분 문자열 집합에 넣어서 그 집합의 크기를 구하면 끝나는 문제이다. 부분 문자열을 찾아내는 방법은, 문자열 슬라이싱을 이용하여 찾아낼 수 있다. 부분 문자열의 길이가 될 수 있는 $len \ sub \ string$을 $1$부터 $len(S)$까지 for문으로..
[Python] 16928번 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 22/11/30 클래스에 못 푼 문제가 있길래 푼 문제이다. 전형적인 BFS문제이지만, 약간의 변형이 필요한 문제로, 그 상황만 잘 처리를 해준다면 쉽게 AC를 받을 수 있는 문제이다. 문제 접근 방식: 처음에 이 문제를 보고 뱀과 사다리를 타는 것이 의무적으로 타는 것이 아닌, 선택적으로 탈 수 있는 것인 줄 알고 의문의 WA를 많이 받았었다. 예를..
[Python] 25635번 자유 이용권 https://www.acmicpc.net/problem/25635 25635번: 자유 이용권 자유 이용권은 놀이공원의 모든 놀이기구를 횟수의 제한 없이 마음껏 이용할 수 있는 이용권이다. 준원이는 ANA 놀이공원의 자유 이용권을 구매했고, 최대한 많이 놀이기구를 이용할 생각이다. www.acmicpc.net 22/11/18 전형적인 그리디 문제로, 그리디 문제 특성상 태그를 안 까면 접근할 때 방황할 수 있기 때문에, 이 문제를 어떻게 접근했는지 알아볼 필요가 있다. 문제 접근 방식: 연속해서 같은 놀이기구를 탈 수 없다는 조건을 보고, 서로 다른 놀이기구를 교대로 타면 많이 탈 수 있을 것이라고 처음에 막연하게 생각했다. 예제 입력 1을 보고, 제일 먼저 타야되는 놀이기구는 이용 횟수가 제일 많이 남..
[Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 22/11/18 BFS문제로, 문제에서 주어지는 그대로 구현한다면 시간초과를 받을 수도 있는 문제다. 이를 유의하며 살짝 아이디어를 가져와야되는 문제다. 문제 접근 방식: 먼저 쿼리의 개수가 최대 $500$개이고, 도시(노드)의 개수가 총 $500$개라는 사실을 주목해보자. 때문에 문제에서 주어진 그대로 임의의 도시($k$번 노드)에서 수도 도시($1$번 노드)로 가는 최단 시간을 구하기 위..
[Python] 17394번 핑거 스냅 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 22/11/18 BFS와 에라토스테네스의 체를 섞은 독특한 문제로, 두 알고리즘을 모두 알고 있다면 어렵지 않게 해결할 수 있는 문제이다. 특히, 이 문제는 1697번 숨바꼭질 문제와 같은 방식으로 방문처리를 하기 때문에 1697번을 해결했었다면 이 문제 또한 쉽게 해결할 수 있을 것이다. 문제 접근 방식: 먼저 목표 범위인 $A$와 $B$의 범위를 보면 $2 \leq A \leq B \leq 100,..
[Python] 23747번 와드 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 22/11/21 BFS문제에 시뮬레이션을 곁들인 문제로, 문제에서 주어지는 상황을 그대로 시뮬레이션하여 쉽게 해결할 수 있는 문제이다. 다만, 파이썬으로 해결하려고 한다면 시간초과에 유의해서 접근해야 풀 수 있는 문제이다. 문제 접근 방식: 먼저, 문제에서 주어진 정보대로 그래프의 크기, 그래프, 한별이의 현재 위치, 여행 기록을 모두 입력으로 받았다. 이후, 한별이의 여행기록을 for문으로 하나하나 돌리며 시뮬레이션을 해보는데, 와드를 놓..

티스토리툴바