본문 바로가기

코딩테스트 문제풀이83

[백준] 14502 연구소 백준 14502번 연구소 그래프 / 완전탐색 / dfs&bfs / 삼성전자 SW 역량테스트 [문제] 그래프에 벽을 3개 세우는 모든 경우의 수를 구해야 하므로, 조합이 필요하다. DFS, BFS, itertools 로 구할 수 있는데 나는 조합 라이브러리인 itertools를 사용해서 구현했다. 전체 맵의 크기가 8x8 이므로, 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우 64C3이 될 것. 이는 100,000보다도 작은 수 이므로 모든 경우의 수를 고려해도 시간안에 해결 가능하다. [과정] 1. graph의 값들을 입력받고 해당값이 2인경우 별도의 리스트(virus_list)에 저장하고 0인경우 해당 인덱스값을 얻기위해 별도의 리스트(map)에 좌표값을 저장 (2차원리스트로 조합 라이브러리를 사.. 2021. 8. 16.
[백준] 21921 블로그 백준 21921번 블로그 투 포인터 / 누적 합 / 슬라이딩 윈도우 [문제] 구간 합 문제 접두사 합을 사용한 알고리즘을 적용하면 효과적 [과정] 각 구간(data)에 대하여 누적 합을 계산한 배열(prefix_sum)을 생성 0에서 부터 x만큼 증가하여 각 x기간 동안의 누적 합을 배열(result)에 저장 result중 최댓값을 출력하고, 해당 최댓값의 개수를 출력 [소스코드] # 블로그 import sys input = sys.stdin.readline n,x = map(int, input().split()) data = list(map(int, input().split())) sum_value = 0 prefix_sum = [0] for i in data: sum_value += i prefix_.. 2021. 8. 16.
[백준] 11659 구간 합 구하기 4 백준 11659번 구간 합 구하기 4 투 포인터 / 누적 합 [문제] 리스트가 주어졌고 구간의 합을 구하는 문제임을 파악하자. 구간의 합 알고리즘을 넣지 않으면 시간초과가 나는 문제이다. 기본적으로 M개의 쿼리가 수행할 때마다 전체 리스트의 구간 합을 모두 계산하는 경우는 O(NM)의 시간복잡도를 가진다. 하지만 N개의 리스트의 각 구간에 대해서 합산값을 미리 구해놓으면 O(N+M)의 시간복잡도를 가진다. 즉, 접두사 합을 이용해 시간초과를 해결할 수 있다. [과정] 리스트의 각 구간에 대해서 접두사 합을 계산하여 배열(prefix_sum)에 저장 쿼리를 수행 [소스코드] # 구간 합 구하기 4 import sys input = sys.stdin.readline n,m = map(int, input()... 2021. 8. 16.
[백준] 11728 배열 합치기 백준 11728번 배열 합치기 투포인터 / 파이썬 [문제] 투포인터의 '정렬되어 있는 두 리스트의 합집합' 문제 문제의 요구사항: 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것 [과정] 정렬된 리스트 a,b를 입력받음 리스트 a에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 함 리스트 b에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 함 a[i]와 b[j] 중에서 더 작은 원소를 결과 리스트에 담음 리스트 a와b에서 더 이상 처리할 원소가 없을 때 까지 2~4번의 과정을 반복 [소스코드] # 배열 합치기 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, inp.. 2021. 8. 13.
[백준] 1167 트리의 지름 백준 1167 트리의 지름 그래프 / 트리 / 파이썬 ㅠㅠㅠㅠ.. 매우 유사한 '1967번 트리의 지름'문제는 이 문제와 같은 방법으로 풀었는데 이건 도저히 풀리지가 않았다... 몇번이나 고치고 고치고 했는지 풀면서 왜틀리지 했지만 역시 컴퓨터가 옳았다.ㅋㅋ 생각보다 시간제한이 힘들었고 예제가 하나뿐이라 이유를 찾기에 좀 힘들었던 문제다. 스터디할때 결국 풀지못했는데 2일이 지난 후 혼자해보다가 풀게되었다. 역시 카페가 공부잘되는 듯ㅎㅎ [문제] 1967번이랑 문제가 같은데 제시된 입력부분이 다름을 확인 알고리즘은 그대로 bfs를 사용함 [과정] 1. 입력값 부분을 첫번째 입력값을 기준으로 graph에 추가시켜줌 2. bfs수행 2-1) 거리(distance)와 방문처리(visited)는 bfs를 돌때마.. 2021. 8. 7.
[백준] 1991 트리 순회 백준 1991번 트리 순회 트리 / 재귀 / 파이썬 [문제] dfs를 사용해서 재귀를 호출하고, 각 순회의 순서에 맞게 노드들을 각자의 리스트에 저장하는 문제 노드가 알파벳으로 주어진다. graph에는 알파벳이 들어가야하고 알파벳에 각자 인덱스를 부여해야한다. [과정] 순회순서를 보자면 전위순회, 중위순회, 후위순회는 각각 루왼우 / 왼루우 / 왼우루의 순서로 감을 확인 할 수 있다. 기본적으로 셋다 왼쪽부터 순회를 돌고 루트노드의 순서가 각각 첫번째, 두번째, 세번째 임을 알 수 있다. 또한 dfs와 bfs의 탐색순서를 보면 dfs를 사용해야함이 보인다. 이후 dfs를 돌리는데 첫째 - 왼쪽조건을 확인하고 노드가 있으면 순회를 돈다. (재귀호출) 둘째 - 오른쪽 조건을 확인하고 노드가 있으면 순회를 돈.. 2021. 8. 7.
[백준] 1967 트리의 지름 백준 1967번 트리의 지름 그래프 / 파이썬 [문제] [과정] ※ 핵심 키워드 : 트리의 지름 구하는 공식 임의의 노드에서 가장 먼 길이에 있는 노드구하기 구해진 노드에서 가장 먼 길이에 있는 노드를 구하기 이렇게 bfs를 두번을 돌게되면 트리의 지름을 구할 수 있다. 만약 for문으로 모든 노드의 수만큼 돌리게 되면 파이썬으로 시간초과가 발생한다. bfs에서 리턴값으로 가장 먼 노드와 해당 노드까지의 길이를 반환한다. 반환된 노드값을 한번 더 bfs를 돌리고 여기서 반환된 길이(dist)를 출력한다. [소스코드] # 1967 트리의 지름 from collections import deque n = int(input()) graph = [[] for _ in range(n+1)] for _ in ran.. 2021. 8. 6.
[백준] 10718 We love kriii 백준 10718번 We love kriii 구현 / 파이썬 [문제] [과정] 기본적인 출력문제 [소스코드] # We love kriii print('강한친구 대한육군', end='\n') print('강한친구 대한육군') [통과] 2021. 8. 5.
반응형

티스토리툴바