전체 글
백준 2667 단지번호붙이기(BFS, DFS)
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 보면 그래프 문제라는걸 바로 알 수 있고 dfs, bfs로 풀어야함을 알 수 있다. 0으로 구분되어져 있는 단지는 몇개인지 모르기 때문에 처음 1을 찾아줘서 거기서 탐색을 진행해 0으로 만들어주면 다음 단지를 찾을 때 방금 탐색했던 단지는 고려하지 않아도 됨을 알 수 있다. BFS 이용 from collections import deque def bfs(x, y): dx = [-1, 1, 0..
백준 18111 마인크래프트
https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 일단 땅고르기를 위해 가장 최소의 시간을 구하기 위해서는 여러 방법이 있었다. 1. ground 2차원 배열에서 중간값을 찾아서 그 중간값을 기준으로 잡고 땅고르기를 하기(이분탐색) ground의 min값 ~ max값 사이의 range를 돌면서 그때 해당하는 조건에 대해서 테스트하는것도 좋은 방법 n, m, b = list(map(int, input().split())) ground = [lis..
백준 1213 & 팰린드롬 알고리즘(Palindrome Algorithm)
Palindrome 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 ex) 기러기, 요기요 def is_palindrome(word): list_word = list(word) for i in range(0, len(list_word) // 2): if list_word[i] == list_word[len(list_word) - 1 - i]: continue else: return False return True slice를 이용하여 문자열을 반대로 뒤집은다음에 비교를 하는것도 매우 좋은 방법이다. https://www.acmicpc.net/problem/1213
백준 1251 단어 나누기
https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 1단어를 3개로 나누고 이거에 최소값을 구해야 한다라고 생각했을 때 방법이 막막했다. 하지만 python의 max, min함수를 통해 모든 조합의 string을 리스트에 넣고 min함수를 때려버리면 좋겠다고 생각했다. 모든조합의 string을 만드려면 3개로 나누는 기준이 필요한데 i j k 3개의 변수를 두고 단어는 무조껀 1개 이상의 문자를 포함하라고 했기 때문에 i : 0 ~ len(data)..
백준 1991 트리 순회
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이문제는 트리구조를 받아서 어떤 형태로 저장시켜서 어떻게 이용할껀지에 대해 요구하는 문제 흔히 알고있는 dfs, bfs 트리구조로 데이터를 2차원 리스트로 받아 처리하려고 하니까 어려움이 있어 Tuple로 처리를 했다 즉, A라는 루트는 left, right의 자식 노트가 있을 것이고 key, value의 값으로 묶는다는 개념으로 접근하면 쉽다 import sys input = sys...