이것 저것 올리는 곳

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제의 3차원 버전 문제다. 문제를 풀..

알고리즘 문제풀이 2023. 9. 23. 22:04

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 BFS공부 후에 처음으로 BFS응용? 문제를 풀어 봤다. 나의 문제 접근 방법은 지도에서 2가 나온 지점을 시작 지점으로 근처에 갈 수 있는 index번호들을 큐에 하나씩 넣어가며 탐색했다. 예시로 0, 0에서 갈 수 있는 index들은 [0,1], [1,0]이 있다. [0,1]에서 갈 수 있는 index들은 [0, 2], [1, 1]이 있고 [1..

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

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 BFS를 공부했다. BFS를 공부하기 전에는 BFS도 재귀 함수를 이용해서 구현하는 게 일방적인 방법일 거라고 생각했었다. 그런데 공부해보니 대부분 그냥 큐랑 반복문을 사용해서 구현하는 것 같다. 문제는 주어진 노드들이 어떻게 연결 되어 있는지 인접리스트를 만들어 주고, 입력에서 주어진 시작 노드를 기준으로 BFS, DFS 탐색하면 된다. 이 문제에서 주..

알고리즘 문제풀이 2023. 9. 7. 22:04

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 이진트리가 주어졌을 때, 리프 노드라는 것의 개수를 구하는 문제다. 나는 이 문제를 풀 때 입력으로 주어지는 부모 노드를 이용해 다음과 같이 인접 리스트를 만들어 준 후에 삭제할 노드를 삭제하고 리프 노드 카운팅을 해줬다. path = [[] for _ in range(n)] for i in range(n) : if node[i] == -1 : root_node = i else : pa..

알고리즘 문제풀이 2023. 9. 1. 23:37

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