https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 💡IDEA 최대 N개의 종류의 알파벳을 가진 연속된 문자열의 길이 최댓값을 찾는 투 포인터 문제 왼쪽 포인터를 기준으로 오른쪽 포인터를 옮기며 해당 문자열 내 몇 종류의 알파벳을 가졌는지 세어주어야 한다. 다른 것보다 시간 초과가 많이 일어나서 경우를 생각해 제외할 수 있는 부분은 모두 제외시켰다. 1. N==1 이거나 입력 문자열의 길이가 1인 경우 → 정답: 1 2. 입력 문자열이 이미 N개의 종류 알..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 💡IDEA 트리, DFS를 사용하는 문제이다. 처음엔 큐를 사용하여 삭제한 노드에 연결된 모든 노드들을 -1로 갱신하여 지워주는 방법으로 풀었으나 99%에서 실패가 떴다. 찾아보니 0번 노드만 남은 경우에도 결과값이 1이여야 하는데, 0으로 출력되고 있었다. 이것을 해결하기 위해 여러 방법으로 수정했으나 도무지 알 수가 없어서 DFS를 사용했다. 삭제한 노드에 연결된 모든 노드들의 부모 노드..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 💡IDEA 조건에 맞게 구현하는 문제이다. 큐를 사용해서 뱀의 몸을 구현하고, 주어지는 방향에 맞게 위치를 틀어준다. 방향은 좌우로 움직이는 것을 고려하여 dir 배열을 사용하여 인덱스 값으로 방향을 조절했다. 가장 먼저 0행 0열부터 뱀이 오른쪽 방향으로 움직인다. 갈 수 있는 곳이라면 뱀의 몸에 추가해주고, 시간을 카운트한다. 만약 해당 위치에 사과가 있다면 사과가 없어지고 꼬리는 유지한다. 하지만 ..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 구해야 하는데, 조건은 해당 번호의 사람이 본인 번호 자리에 앉거나, 앉지 않거나 두 경우가 존재한다. 가짓수는 몇 번의 반복을 통해서 규칙을 찾을 수 있다. N = 1 N = 2 N = 3 N = 4 N = 5 경우 1 12 21 123 213 132 1234 2134 1324 1243 2143 12..
https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 💡IDEA DFS, 백트래킹을 사용하는 문제이다. 숫자를 직접 하나씩 부등호에 따라 넣어주는 식의 브루트 포스가 가능하다. 백트래킹으로 0~9 숫자를 포함하고 포함하지 않고를 결정하며 부등호를 만족하는 수를 찾으면 된다. 레벨(깊이)가 0이거나 방문하지 않았고 두 수(들어가는 숫자 중 마지막 수, 현재 인덱스 값)를 부등호로 비교했을 때 정상적인 경우에 백트래킹을 수행한다. 현재 인덱스 값을 포함한 값으로 재..
https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 2022.07.14 - [Algorithm/BOJ] - [BOJ][python] 11052. 카드 구매하기 문제에서 최대 금액으로 카드를 구매하는 것을 풀었는데, 이번엔 최소 금액으로 구매 해야한다. 풀이 방법은 거의 비슷한데, 최소 금액을 구하기 위해 min_tmp로 최솟값을 갱신하여 카드 i개를 구매하는 비용을 계산한다.초기 min_tmp값은 적당히 큰..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 처음에는 커서를 움직이며 한 배열에서 pop과 insert 연산을 사용했는데, 시간 초과가 발생했다. 쉽게 커서를 구현하려면 스택을 사용하면 된다. 기존 입력받은 배열(arr)과, 커서 뒤의 배열을 위해 스택용(arr_tmp)을 만든다. 커서의 왼쪽은 arr, 오른쪽은 arr_tmp라고 생각하면 편하다. 연산의 종류에 따라 두 배열에 append 및 pop을 통..
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 💡IDEA 집합을 사용하는 문제이다. 쉽고 빠르게 집합을 구현하기 위해 크루스칼 알고리즘을 사용했다. 집합의 부모를 찾는 함수와 합집합 연산을 하는 함수를 만들었다. 연산이 0인 경우에 합집합을, 1인 경우에는 a의 부모와 b의 부모가 같은지 판단하여 출력한다. 📌CODE import sys input = sys.stdin.readline sys.setre..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 가로 세로가 50 이하이므로 브루트 포스를 더불어 사용했다. 육지(L)인 곳 중 상하좌우로 이어진 곳 중 최단 거리로 이동할 수 있어야 한다. 거리를 재기 위해 큐에서 카운트를 세어준다. 반환 값은 계산한 거리 중 가장 큰 값을 반환한다. 모든 행렬을 순환하면서 모든 육지(L)를 확인하며 최단 거리로 이동하는 시간을 갱신하여 출력한다. 📌CODE import s..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 시작 층(S)에서 시작하여 도착 층(G)까지 U씩 올라가거나 D씩 내려가며 몇 번만에 다다를 수 있는지 판단해야 한다. 버튼을 누르는 횟수는 방문 배열을 사용하여 구하도록 했다. F층 이내에 있는 층 중 방문하지 않은 층을 방문하며 횟수를 세어준다. 도착 층(G)에 다다르면 방문 배열로 센 횟수에서 -1을 해서 출력한다. 첫 시작을 1로 했기 때문에 -1을 해줘야 함을 ..
