본문 바로가기

Archived(CSE Programming)/알고리즘(Python)

 (17)
프로그래머스 - 네트워크(파이썬, LV3) / 탐색(DFS) https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 문제는 간단한 DFS 문제이다. LV3의 난이도가 아닌거 같은데 여튼, 섬 개수 찾기와 같은 유형의 문제이다. DFS를 통해 방문할 수 있는 곳을 전부 방문하고 방문하지 않은 곳이 있으면 다시 DFS를 호출하면서 전체를 탐색할 동안 DFS를 몇 번 호출했는지를 찾으면 된다. def solution(n, computers):..
미로탈출(파이썬) / 탐색(BFS) 문제 동빈이는 N * M 크기의 직사각형 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4= M: continue # 벽 체크 if graph[next_x][next_y] == 0: continue # 처음 방문시 거리 증가 if graph[next_x][next_y] ==..
음료수 얼려먹기(파이썬) / 탐색(DFS) 문제 N * M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. "INPUT" 00110 00011 11111 00000 "OUTPUT" 3 입력 첫 번째 줄에 얼음 틀의 새로 길이 N과 가로 길이 M이 주어진다.( 1
프로그래머스 - 구명보트(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42885?language=cpp 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이의 핵심은 모든 사람이 보트 1개씩 필요하다고 초기값을 둔다. 그리고 전체 사람들의 무게를 정렬해서 가장 무거운 사람과 가장 가벼운 사람 순으로 같이 갈 수 있는지 같이 갈 수 있을 경우 보트 수를 1개 뺀다(같이 타므로). 이런식으로 전체 사람들을 탐색하여 가장 가벼운 사람과 무거운 사람이 만나는 지점에 달..
프로그래머스 - 큰 수 만들기(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3# 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이 문제는 그리디로 현재 최상의 값을 계속 골라나가면 된다. 그런데, 최상의 값을 찾기 위한 탐색 범위를 계속 한정지어서 풀려고 했다. 그러나 그렇게 풀어버리니 아래 테스트 케이스의 시간 복잡도를 극복하지 못했다. O(N^2)이 되버린 것이다. "INPUT" number = "1234567890"*100000 k = 999999 "OUTPUT" answer = "99999...." 그래서 결국 다른 풀이를 찾아봤다. (출처 : scarletbreeze의 블로그) 핵심은 O(N)이 되도록 문자열을 한 번씩 파..
프로그래머스 - 조이스틱(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42860?language=python3 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 먼저 strSol을 'AAAA....' 로 두고 시작점 cursor는 0이다. 이 때 strSol cursor의 위치에 해당하는 name 값으로 변경하고, 현재 가장 가까운 A가 아닌 name의 문자열의 위치로 가서 strSol을 바꾼다. 여기서 그리디는 2가지가 된다. 상하의 값 중 현재 가장 최소값으로 변경한..
프로그래머스 - 순위(파이썬, LV3) https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 정답 출처 : 멍토의 IT블로그 와샬플로이드 알고리즘으로 접근하는 방식 그러나, 그렇게까지 생각이 안나서, 로직만을 생각했다. 로직은 맞았으나 구현방식이 계속 틀려서 정답을 참조했다ㅠㅠ win[i] -> {} i가 이긴 사람들 집합 lose[i] -> {} i를 이긴 사람들 집합 의 리스트를 준비하고 경기결과를 전체 파싱해서 채워 넣는다. 그리고 이제 i를 이긴 사람들에게 이긴 사람들은 전부 i를 이길 수 있다 또한 i에게 진사람들은 i가 진사람들에게도 전부 진다. 이..
프로그래머스 - 자물쇠와 열쇠 (파이썬, LV3) https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 2020 KAKAO 문제 간과했던 내용 Lock과 Key의 크기가 다를 수 있던 점 Board(전체 배열)의 크기는 Lock의 2배가 아닌 3배여야 한다는 점 회전 배열이 바로 안떠올랐던 점(값을 적어서 확인해봄) 돌기끼리 부딪혀도 안된다는 점(무조건 매끄러운 1이 되야함, 2도 안됨) 풀이 자물쇠 3배 크기의 전체 배열을 구성한다. 해당 전체 배열에서 자물쇠를 중간(start~end) 부분에 값을 옮긴다. 그..

티스토리툴바