티스토리

풀스택챌린지

검색하기

블로그 홈

풀스택챌린지

kimmeh1.tistory.com/m

웹 풀스택 개발자를 향해 공부 중입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[SWEA 2105] 디저트 카페 접근 사각형을 그리기위해 시작 위치를 기준으로 (1, -1), (1, 1), (-1, 1), (-1, -1)로 순서대로 이동하도록 구현하였다. DFS로 탐색을 진행하고 범위를 벗어나거나 이미 방문한 카페라면 return을 하고 그렇지 않을 때는 현재 방향을 그대로 이동하거나 방향을 증가시켜 이동한다. 방향을 증가시켜 이동할 때는 (-1, 1)로 이동하다가 (1, 1) 방향에 목적지가 있을 때 방향을 바꾼다. 또한 (1, -1)이거나 (1, 1)일 때는 현재 방향으로도 이동하고 다음 방향으로도 이동할 수 있도록 재귀호출한다. 구현 - 주어진 입력을 모두 받은 후에 - board를 탐색하면서 각 위치에서 dfs를 진행한다. N = int(input()) board = [list(map(int, input().. 공감수 0 댓글수 0 2021. 9. 28.
[SWEA 1949] 등산로 조성 접근 최대 높이를 찾고 2차원 맵을 탐색해서 최대 높이의 위치에서 DFS를 진행한다. 현재 위치에서 상하좌우 탐색을 진행하고 현재 위치보다 높이가 작은 위치로 이동한다. 만약 같거나 클 때는 K만큼 공사할 수 있는지 판단하여 이동한다. 구현 - 최대 높이를 찾아서 max_value에 저장한다. - 2차원 리스트인 board를 탐색해서 max_value가 나올 때마다 dfs를 진행한다. - dfs에는 현재 위치, 방문 여부, 길이, 공사의 여부를 전달한다. N, K = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] max_value = 0 for y in range(N): for x in range(.. 공감수 0 댓글수 0 2021. 9. 13.
[SWEA 2382] 미생물 격리 접근 리스트를 원소로 갖는 2차원 리스트를 생성하여 미생물들의 개수와 방향을 넣었다. 이후에 미생물이 이동할 때 새로운 2차원 리스트에 이동한 미생물들을 대입하였다. 그리고 2개 이상의 미생물들이 모였을 때 합을 구하고 제일 많은 개수를 갖는 미생물의 방향을 구하여 업데이트하였다. 구현 - 다음은 미생물들이 이동하는 것을 구현한 함수이다. - 먼저 기존의 미생물들이 들어있는 board를 탐색하여 해당 미생물을 이동시킨다. - 이동시켰을 때 약품이 칠해져있는 곳일 때는 개수를 반으로 나누고 방향을 반대로 설정한다. - 미생물의 개수가 1 이상일 때 새로운 위치에 대입한다. - 모든 미생물들의 이동이 끝난 후에 2개 이상이 모여있는 곳은 미생물들을 하나씩 꺼내어 총합을 구한다. - 이때 개수가 가장 많은 미.. 공감수 0 댓글수 0 2021. 9. 12.
[SWEA 2112] 보호 필름 접근 약품을 투입할 수 있는 모든 조합을 확인했을 때 완전탐색으로 풀이가 가능하다고 생각하였다. 따라서 K가 2 이상일 때 약품을 투입하는 조합을 생성하여 해당 셀을 모두 0 또는 1로 바꾸어주었다. 그리고 모두 성능검사에 통과하는지 판단하는 함수로 전달하여 판단하였다. 이 문제는 계속 49개만 맞았다고 나왔는데 문제점을 파악하기 어려웠다. 계속 시도를 해보다가 뒤늦게 깨달았는데 나의 풀이에 문제가 있었다. 만약 3개의 막에 약품을 주입한다했을 때 해당 막의 셀들을 모두 0 또는 1로 바꾸어주었다. 하지만 이렇게하면 3개의 막 중에 2곳은 0 1곳은 1을 주입할 수도 있는 경우의 수를 놓치고 있었다. 따라서 이 부분을 해결한 후에 PASS를 받을 수 있었다. 구현 - 성능 검사에 통과할 수 있는지 판단하.. 공감수 0 댓글수 0 2021. 9. 10.
[SWEA 5644] 무선 충전 접근 두 명의 사용자가 이동을 할 때마다 주위에 충전할 수 있는 충전기를 모두 찾는다. 찾은 후에 성능을 기준으로 내림차순 정렬하여 두 명의 사용자가 최댓값이 되도록 충전기를 선택하도록 한다. 만약 같은 충전기 내에 두 명이 존재하면 배분을 해서 가져가야한다. 하지만 한 명이 다른 충전기 범위 내에도 존재하면 이 사용자는 다른 충전기를 선택하도록 해야한다. 구현 - 사용자 2명의 이동 경로를 move_info에 저장한다. - 충전기의 정보를 charge_info에 저장한다. - 이제 사용자들을 move_info에 기반하여 이동시키고 - 이동시킬 때마다 charge 함수로 위치를 보내서 최댓값으로 충전할 수 있는 양을 구한다. for tc in range(test_case): N = 10 M, A = ma.. 공감수 0 댓글수 0 2021. 9. 6.
[SWEA 2383] 점심 식사시간 접근 먼저 계단은 무조건 2개가 존재하고 사람의 수는 10명 이하이다. 따라서 완전탐색으로 풀 수 있었다. 최대 10명의 사람들이 1번 또는 2번 계단을 고르는 모든 경우의 수를 만들고 같은 계단을 고른 사람들 끼리 그룹을 만들어 해당 그룹의 사람들이 계단을 타고 모두 내려오는 시간을 구하는 함수를 만들었다. 이를 통해 1번과 2번 계단을 선택한 사람의 소요시간을 구하고 이 중 최댓값을 찾아 최종해와 최솟값 비교를 진행한다. 구현 - DFS를 통해 사람들의 1번 또는 2번 계단을 고르는 모든 경우의 수를 구한다. - 사람들이 모두 계단을 골랐으면 1번 계단을 고른 사람과 2번 계단을 고른 사람을 나누고 이를 solve함수에 전달한다. - solve 함수에서는 해당 사람들이 모두 내려왔을 때의 시간을 구하.. 공감수 0 댓글수 0 2021. 9. 1.
[SWEA 4014] 활주로 건설 접근 먼저 가로와 세로를 탐색해서 활주로가 가능한지 알아보기 위해 각 열의 세로 정보들을 N행에 이어 붙였다. 이후 각 행마다 활주로 건설이 가능한지 검사를 한다. 먼저 이전 인덱스의 값과 현재 인덱스의 값이 같을 때는 continue를 진행한다. 이전 인덱스와 현재 인덱스의 + 1 값이 같을 때는 내리막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 이전 인덱스의 - 1과 현재 인덱스의 값이 같을 때는 오르막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 경사로를 설치할 때는 범위를 벗어나거나 겹쳐서 사용하면 안되기 때문에 각 인덱스에 경사로 설치유무를 체크하고 맵을 벗어나는지 체크하여 경사로를 설치하도록 한다.. 공감수 0 댓글수 0 2021. 7. 29.
[SWEA 5653] 줄기세포배양 접근 X시간 비활성화 상태 -> X시간동안 활성화 -> 죽음, 활성화 후 1시간 동안 번식을 한다고 한다. 이를 구현하기 위해 다음과같이 접근하였다. 만약 X = 2 라고 해보자. X에 2를 곱하면 4가 되고 4초 = 초기상태 3초 = 비활성화 2초 = 활성화 1초 = 활성화 및 번식 0초 = 죽음 위와 같이 X에 2를 곱하면 X - 1이 되는 시점에 번식이 이루어진다. 이렇게 비활성화 -> 활성 -> 번식을 구현하였다. 이제는 동시에 같은 곳에 번식을 하려고할 때 X가 큰 것이 오도록 해야한다. 이를 위해 X순으로 내림차순 정렬 후에 X가 큰 것부터 처리하도록 하였다. 이를 통해 먼저 처리가 되어있거나 이미 줄기세포가 있다면 continue가 진행되어 더 낮은 X는 같은 곳에 번식이 되지 못하도록 구현.. 공감수 0 댓글수 0 2021. 7. 28.
[SWEA 2115] 벌꿀 채취 접근 두 명의 일꾼이 각각 가로로 연속으로 M개의 벌통을 선택한다. 이때 두 명의 일꾼이 선택한 벌통이 겹치면 안된다. => 이는 2차원 리스트의 완전탐색을 통해 두 명의 일꾼이 벌통을 선택하는 경우의 수를 구할 수 있을 것이다. 선택한 M개의 벌통 중에서 가중치가 가장 큰 것을 찾아야한다. 예를 들어 5, 5, 9 벌통을 선택했고 C가 10이라고 하자. 그렇다면 최대 수익을 위해 5, 5가 아닌 9를 선택해야한다. => itertools의 combinations를 활용하여 선택한 벌통 중에 최대수익을 찾는다. 구현 - 벌통을 2개 선택했을 때 최대수익을 구한다. - 두 명의 일꾼이 선택한 벌통(storage[0], storage[1])에서 combinations를 통해 최대수익을 구한다. - 이를 re.. 공감수 0 댓글수 0 2021. 7. 27.
[SWEA 2117] 홈 방범 서비스 첫 번째 접근 모든 위치에 대해 BFS를 진행하였다. BFS를 하면서 집의 개수를 카운트하였고 집의 개수 x M이 운영비용보다 같거나 클 때 최댓값 비교를 진행했다. PASS는 되었지만 시간이 오래 걸렸고 불필요한 곳까지 탐색한다는 것을 알았다. 첫 번째 구현 - K를 N+1 ~ 1까지 탐색하면서 모든 좌표에 대해 BFS를 진행한다. - BFS는 현재 위치를 기준으로 거리를 통해 방문표시를 한다. - 거리가 K이하일 때만 큐에 넣어 다음 위치를 탐색할 수 있도록 하였다. => 마름모 형태 - 이후 현재 위치가 집일 경우 집의 개수인 count를 증가시켰다. - BFS가 종료되고 count x M이 운영 비용보다 크거나 같을 때 최댓값 비교를 한다. from collections import deque d.. 공감수 0 댓글수 0 2021. 7. 20.
[다익스트라] 1249 보급로 NxN의 맵이 있다. (0, 0)에서 출발해서 (N-1, N-1)까지 이동을 하려고하는데 중간중간에 도로들이 파손이 되어있다. 파손된 도로를 복구하는데 걸리는 시간은 각 칸에 적힌 수만큼 걸린다. 도로를 이동할 때 걸리는 시간을 제외하고 출발지부터 도착지까지 복구하면서 이동할 때 걸리는 시간이 최소인 시간을 구하라. 접근 - 기본적으로 다익스트라를 적용시켰다. - 2차원 맵이기 때문에 현재위치에서 상하좌우 칸에 대한 시간을 구하여 최솟값을 갱신해나간다. 구현 - 2차원 맵에 대한 정보를 입력받아 graph라는 2차원 리스트에 저장한다. - 이후 solve함수에서 해를 구하여 반환한다. - 다음은 solve함수에 대한 코드이다. - 먼저 각 칸을 INF로 초기화하여 나중에 최솟값으로 갱신될 수 있도록 한다.. 공감수 0 댓글수 0 2021. 4. 25.
[다익스트라] 5251 최소 이동 거리 어떤 도시에 E개의 일방통행 도로가 있고 각 구간이 만나는 연결지점에 0번부터 N번까지의 번호가 붙어있다. 이때 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 구하라. 다익스트라 알고리즘 - 다음 방문하는 노드에 대한 경로를 지금까지 기록한 정보를 통해 최솟값을 갱신한다. - 기록되어있는 정보에는 출발점부터 해당 번호까지 왔을 때의 최솟값이 저장되어있으며, 계속 갱신될 수 있다. 구현 - 2차원 리스트로 그래프를 표현한다. - 초기에 INF 값으로 초기화한 이유는 이후에 그래프를 탐색하면서 최솟값을 찾을 때 연결되어있지 않은 그래프는 최솟값의 후보에서 벗어나도록 하기위함이다. - E개의 일방통행 도로를 입력받아 그래프에 저장한다. V, E = map(int, input().spl.. 공감수 0 댓글수 0 2021. 4. 25.
[프림] 5249 최소 신장 트리 0번부터 V번까지의 노드가 있고 E개의 간선이 주어지는 그래프가 있을 때 최소신장트리를 구성하는 가중치의 합을 출력한다. 프림 알고리즘 - 특정 정점을 시작으로 점진적으로 최소신장트리를 완성해나간다. - 지금까지 선택한 정점을 검색하여 아직 선택하지않은 정점 중에 가중치가 가장 적은 정점을 선택한다. 구현 - 정점의 개수(V)와 간선의 개수(E)를 입력받는다. - 간선의 개수만큼 노드a, 노드b, 가중치w를 입력받아 2차원 리스트로 그래프를 표현한다. V, E = map(int, input().split()) graph = [[0 for _ in range(V+1)] for _ in range(V+1)] for _ in range(E): a, b, w = map(int, input().split()) g.. 공감수 0 댓글수 0 2021. 4. 25.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.