Algorithm problems, coding test (19) 썸네일형 리스트형 [백준][10451][S2] 순열 사이클 기본적인 DFS 문제이며, 연결된 부분집합의 개수(사이클)을 세는 문제이다. DFS를 한 번 호출할 때마다 count를 1씩 올려서 개수를 센다. import sys T = int(sys.stdin.readline()) for i in range(T): N = int(sys.stdin.readline()) graph = list(map(int, sys.stdin.readline().split())) #graph는 1번 인덱스부터 사용한다. 0번은 더미 데이터를 넣어주자. graph.insert(0, 99999) #방문 기록 visited = [False for i in range(N+1)] visited[0] = True #---------------------------------------------.. [백준][11724][S2] 연결 요소의 개수 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 기본적인 DFS 알고리즘에 "연결 요소의 개수"를 세는 기능을 추가한다. DFS가 한 번 호출될 때 마다 연결 요소는 하나씩 늘어나게 만들면 된다. import sys sys.setrecursionlimit(5000) N,M = map(int, sys.stdin.readline.. [백준][1259][B1] 펠린드롬수 문제 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. 출력 각 줄마다 주어.. [백준][1181][S5] 단어 정렬 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 사실 간단한 구현 문제는 머리를 쓰지 않아도 어떻게든 구현은 할 수 있다. 단지, 숙련도에 따라 코드를 얼마나 효율적으로 작성할 수 있는지가 문제이다. 따라서 직접 구현할 수도 있었지만, 다른 사람이 어떻게 효율적으로 코드를 구현하였.. [백준][1018][S5] 체스판 다시 칠하기 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8.. [백준][1157][B1] 단어 공부 [문제] 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. [입력] 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. [출력] 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 파이썬 숙련도에 따라 코드가 천차만별로 변할 수 있는 문제이다. 그동안 배운 문법으로 구현해보자. answer = '' S = input() S = S.upper() alpha_list = ['A','B','C','D','E','F','G','H','I','J','K.. [이코테][Chapter 5][문제] 4. 미로 탈출 [문제설명] N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다. [입력조건] 첫째 줄에 두 정수 N, M(4 [이코테][Chapter 5]DFS, BFS 재귀 : 하나의 함수를 n,n-1,n-2,... 인자를 바꾸어가며 반복하는 것을 의미한다. "스택" 형태로 작용한다. 스택 : 선입후출. 상자 쌓기와 동일 큐 : 선입선출. 에스컬레이터와 동일 그래프 : 노드끼리 연결 관계를 표현한 자료형을 의미 DFS : 그래프에서, 한 노드를 계속 파고들면서 탐색하는 방식. 위의 그래프에서는 A-B-C-D-... 순이 된다. def dfs(graph, v, visited): #현재 노드를 방문 처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드르 재귀적으로 방문 for i in graph[v]: #그래프 1번 노드 시작. 2,3,8 방문 if not visited[i]: #방문하지 않았다면? dfs(graph, i, .. 이전 1 2 3 다음 목록 더보기
