이것 저것 올리는 곳

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 DFS혹은 BFS로 풀면 되는 문제다! 아직 BFS를 어떻게 짜야하는지 잘 모르므로 DFS로 짰다. 이 문제를 풀기 위해서 check 리스트만 잘 만들어 주면 쉽게 풀 수 있는 문제였던 것 같다. check리스트의 크기는 입력값과 똑같이 만들어 주면 된다. 값들은 전부 0으로 초기화 해줬다. 중첩 for문으로 입력된 정사각형 모양의 리스트를 하나하나 탐색하는데, 이때 입력받은 리스트(입력 값)..

알고리즘 문제풀이 2023. 8. 29. 19:15

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 처음 문제를 읽고 계단 오르기랑 비슷한 문제인가? 싶었는데 알고리즘 분류를 보고 전혀 아니라는 걸 알았다. 우선 규칙을 찾기 위해 노가다를 했다. 적다 보니 규칙이 보이기 시작했다. 규칙은 알 것 같은데 식을 도저히 어떻게 세워야 할지 감도 안 와서 저기 나오는 수들을 string으로 하나씩 만들어서 총 문자열 개수를 셀까 싶었다... 이건 좋은 ..

알고리즘 문제풀이 2023. 8. 18. 01:35

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 문제 좀 어려웠던 백트레킹 문제다. 그러나 백트레킹 문제답게 넉넉한 시간, 넉넉한 메모리이 주어진다. 이는 효율성은 죽 쒀서 개 줘도 정답이 나올 가능성이 높다. 그래서 정답 비율이 높은 듯하다. 숫자들은 앞에서부터 차례대로 계산하면 되니 내버려두고 연산자만 모든 경우의 순열을 구하면 된다고 이해했다. 문제를 다 풀고 질문게시판 가보니 연..

알고리즘 문제풀이 2023. 8. 16. 00:55

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 스택만 알면 쉽게 풀 수 있는 문제인 것 같다! 정답 비율이 낮은 이유는 아마 스택을 사용하지 않고 문자열이 폭발할 때마다 문자열 전체를 다시 반복 돌리는 코드를 제출한 사람이 많아서 그런 것 같다. 나도 처음에 문자열이 폭발할때 마다 다시 문자열 전체를 반복 돌려서 비교할까 했지만 입력 조건을 보면 문자열의 최대 길이는 100만이다. 100만을 몇번이나 반복을 해야 할 테니 ..

알고리즘 문제풀이 2023. 8. 11. 21:00

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 노가다 문제다 쉽게 풀 수 있을지 모르겠는데, 난 노가다로 풀었다. 이 문제에서 나는 기준점을 어떻게 잡아야 할지 부터 생각했다. (회전하는 고리가 총 몇개가 만들어질 수 있는지) 예를 들어 4, 4의 배열이라고 하면 2개의 회전 고리가 만들어질 수 있다. 5, 4의 경우도 마찬가지다. 6, 6의 ..

알고리즘 문제풀이 2023. 8. 11. 00:08

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 이게 어떻게 실버 3 문제인가? 두 시간 녹여준 문제다 처음에는 재귀로 풀었다가 메모리 초과가 났다. 그래서 DP로 풀어보려고 마음먹고 문제를 풀었는데 import sys n = int(input()) arr = [] ans_arr = [] for i in range(n) : arr.append(int(sys.stdin.readline().rstrip())) i = n - 1 count = 0 while..

알고리즘 문제풀이 2023. 8. 9. 23:29

https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 문제 제시된 원소가 하나씩 밖에 없어서 헷갈렸던 문제다... 여러 개의 큐가 하나의 큰 큐가 된다는 것만 이해한다면 쉽게 풀 수 있는 문제다. 예제 입력 1을 예시로 두번째 입력 0 1 1 0을 보면 1번 4번만 큐이고 3번 4번은 스택이다. 그다음 각 자료구조에 들어있는 원소들은 1 2 3 4 삽입될 원소들은 2 ..

알고리즘 문제풀이 2023. 8. 4. 21:18

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 삽질 엄청한 문제다. 문제가 제목값 하는 문제다. 나에게 도움이 된 반례는 1 D 1 [] 정답 : error 1 R 1 [] 정답 : [] 오답 반례를 찾아보며 여러번 수정한 끝에 맞출 수 있었다. 코드 길이를 보면 알겠지만 반례를 찾아가며 코드가 한줄한줄 늘어났고, 늘어난 코드에서 필요없는 부분들을 지우다 보니 이렇게 됐다. 저기 제일 긴 코드도 내가 찾아본 모든 반례가 통과하긴 했다. from collections import deque im..

알고리즘 문제풀이 2023. 7. 26. 00:44