생각하다 생각하다

4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net >문제 >접근방법 결국 섬의 개수를 세는 거니까 정사각형을 전체에서 섬이 있는 곳을 발견 할 때마다 재귀 dfs로 탐색하고 발견하면 count를 1 더하면 된다. 재귀 dfs 함수 안에서는 상하좌우 대각선 네 방면까지 탐색하고 방문한 경우에는 0으로 바꿔준다. >풀이법 주석으로 대체 >코드 # 런타임 에러 (RecursionError) 방지 import sys sys.setrecursionlimit(10**6) # 좌표가 (0, 0)일 때를 기준으로 상하좌..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net >문제 >접근방법 트리도 그래프의 유형 중 하나이기 때문에 bfs를 이용한다. 부모노드에 인접한 노드를 자식노드로 간주하고, 자식노드 인덱스의 값을 부모노드로 채워준 리스트를 만들어서 출력하면 된다. >풀이법 주석으로 대체 >코드 from collections import deque n = int(input()) # 노드의 개수 tree = [[]*n for _ in range(n+1)] # 트리의 노드 정보 queue = deque([]) # 큐의 원소는 부모노드의 역할 visited = [False for _ in rang..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net >문제 >접근방법 감이 상하좌우의 감을 익히기 때문에 깊이우선탐색을 사용한다. 하루가 지날 때마다 감이 있는 위치에 1을 더해준다. bfs가 끝났을 때 가장 큰 숫자가 토마토가 모두 익을 때까지의 최소 날짜이다. >풀이법 1. 2차원 리스트 box 생성 후 상자에 담긴 토마토들의 정보를 입력받는다. 2. 상자 중에서 1이 담긴 모든 위치를 큐에 삽입한다. (이때 좌표를 입력받으므로 큐의 요소는 리스트([])로 생성한다) 3. 큐의 원소를 꺼내 좌..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net >문제 >접근방법 2차원 리스트에 밭을 구현하고 배추를 심은 곳에만 1을 넣는다. 1인 곳에서 상하좌우를 탐색해서 배추흰지렁이 마리 수 세기. >풀이법 1. 밭의 크기만큼 2차원 리스트를 생성한다. 2.입력받은 배추 위치에 1을 넣어준다. 3. 밭을 반복문으로 인덱스 하나씩 검색해서 1인 경우에 search함수를 실행한다. 4. search함수는 1의 상하 좌우가 0 일 때까지 재귀적으로 탐색하고, 탐색이 끝난 자리는 0으로 값을 변경해준다. 5. search가 한 번 수..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net >문제 >접근방법 그래프 탐색 dfs, bfs 사용하기 >풀이법 1) 깊이우선탐색(반복)[DFS] 1. 2차원 리스트 생성 후 입력값 append 2. dfs함수 - 스택을 이용한 깊이우선탐색 수행 3. dfs의 리턴값 visit의 개수에서 1을 뺀 값 출력 2) 깊이우선탐색(재귀)[DFS] 1. 2차원 리스트 생성 후 입력값 append 2. dfs함수(재귀) - dfs함수를 재귀적으로 호출 3. visit 대신 한 번 dfs를 수행할 때마다 count에 1을 더해..

1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net >문제 >접근방법 시간초과를 면하려면 모든 문자열을 검사하는 것이 아니라 중복된 문자를 모두 빼고 남은 문자열을 검사해야한다. count로 알파벳 개수를 세고 temp보다 크면 temp에 넣는다. >풀이법 1. ch에 문자열을 입력받은 후 모두 대문자화 해준다. upper() 2. ch2에 입력받은 문자열에서 중복을 제거해서 넣어준다. join(set()) 3. ch2의 모든 요소의 개수를 세고 비교해보면서 가장 큰 값은 temp에 넣는다. 4. temp가 갱신될 때마다 ch2[i]를 out에..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net >문제 >접근방법 insert나 replace를 이용하면 시간초과가 나온다. 대신 스택을 이용해서 한 글자씩 스택에 넣고 폭발문자열이 있으면 pop을 해주는 방식으로 푼다. >풀이법 1. 입력받은 문자열을 스택에 하나씩 append 할때마다 폭발문자열과 비교한다. 2. 폭발 문자열의 길이만큼 스택의 크기가 길어지면 3. 스택과 폭발문자열 각각 끝부분부터 비교한다. 4. 폭발문자열의 길이만큼 전부 같으면 그 길이만큼 pop 해준다. (폭발 문자열 ..

5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net >문제 >접근방법 (삽질ver) cursor 위치를 나타내는 변수로 새 리스트에 insert(cursor, pw[i]) 하기 => list.insert의 시간복잡도때문에 시간초과가 뜬다. (제출ver) 리스트 두개를 만들고 사이에 커서를 둔다. 를 입력받으면 오른쪽 리스트의 끝 문자를 왼쪽 리스트에 append한다. >풀이법 1. 왼쪽과 오른쪽 두 개의 리스트를 만든다. 2. 입력받은 문자열의 요소가 < 이면 왼쪽 리스트의 마지막 요소를 오른쪽 리스트에 ..