본문 바로가기

Algorithm

[Baekjoon]백준 11723 집합(실버 5) - Python 문제를 살펴보면 간단하다 주어진 명령에 따라 그에 맞게 연산하는 코드를 작성하면 된다주의할 점은 하나의 명령어(all, empty)인 경우도 있고 두 개의 명령어를 입력하는 경우도 있기 때문에각각의 상황에 맞게 적절하게 처리되어야한다그래서 일단 둘을 합쳐서 입력받고(input().strip().split()) 만약 입력받은 명령어의 길이가 1이라면all 또는 empty라는 뜻이므로 그에 맞게 집합을 세팅해준다만약 그게 아니라면 두번째 명령어(숫자)를 int형으로 변환하여 하나의 변수에 저장해주고add, remove, check, toggle 각 명령어에 맞게 실행하도록 하면된다여기서 주의할 점은 remove를 사용하게 되면 없는 숫자를 제거하려고할 때 오류가 발생하기 때문에discard()를 사용해야 오.. 더보기
[Baekjoon]백준 2696 중앙값 구하기(골드 2) - Python 문제를 살펴보면 M개의 수를 입력받아 홀수번째 index일때의 중앙값을 출력해야한다당연히 이전문제처럼 가장 간단한 방법은 모든 값을 저장하여 index에 따라 값을 찾는 것이겠지만, 정해진 시간과 메모리 안에서 해결하기 위해서는 다른 방법을 사용하여야한다 처음에는 하나의 힙으로 해결이 되는줄 알고 작성하다보니 중요한 점이 있었다중간값을 출력해야하기때문에 하나의 힙으로는 조금 구현이 힘들것같아서 최대힙과 최소힙을 구현하였다중간값은 최대힙에 저장하되, 음수로 저장하여 중앙값이 저장되게 하였고 최소힙에는 중간값보다 큰 값을 저장한다이렇게 되면 최대힙에는 중간값보다 작은 값들이 음수로 큰 값부터 저장될것이고,(Ex -5, -3, -1)최소힙에는 중간값보다 큰 값들이 저장될것이다(Ex 7, 8, 9)대신 값을 그.. 더보기
[Baekjoon]백준 2075 N번째 큰 수(실버 3) - Python 문제를 살펴보면 N을 입력받아 N^2개의 수를 입력받고 N번째로 큰 수를 찾는 문제이다사실 제일 간단한 방법은 우리 모두가 알고있다 모든 값을 배열에 입력받아 sort를 통해 정렬하고이후 해당 index의 위치에 있는 값을 들고오면 된다허나, 우리에게는 시간과 메모리는 한정적이기 때문에 해당 방법은 지양하는 것이 좋다 파이썬에는 heapq라는 모듈이 존재하는데, 이를 활용하면 문제를 어렵지않게 해결가능하다우선, 첫번째 줄의 내용은 그대로 읽어와서 heappush()로 저장을 해준다이후 두번째 줄부터는 다른 조건이 필요한데, 해당 리스트에는 heappush()로 인해 작은 값부터순서대로 저장되어있을것이다 그렇다면 리스트에 저장된 가장 작은 값보다 입력받은 값이 더 크다면해당 리스트를 갱신해야한다 즉, if.. 더보기
[Baekjoon]백준 24480 알고리즘 수업 - 깊이 우선 탐색 2(실버 2) - Python 이전에 풀이한 문제 백준 24479와 굉장히 유사한 문제이다 대신 문제에서 알려준 의사 코드를 보면24479와 다르게 내림차순으로 정점 번호를 방문하는 것을 확인할 수 있다 문제 제출만 하는 것이 아니라 공부를 하는 것이 목적이므로 천천히 코드를 곱씹어보며 작성하였다일단, 정점의 수, 간선의 수, 시작 정점을 받아온 후, 양방향 간선 정보를 받아온다이 과정을 하기 위해 이전에 graph 리스트를 선언하여 입력받은 간선 정보를 저장하도록 해야한다이후 dfs함수를 호출하면 되는데 해당 함수는 먼저 방문 순서를 기록해준다cnt변수를 전역 변수로 선언하여 추가적으로 함수의 인자를 받지 않도록 하였다이후 해당 위치에서의 graph를 내림차순으로 정렬하고 for문을 통해 방문하지 않은 곳을 찾아방문함과 동시에 cn.. 더보기
[Baekjoon]백준 24479 알고리즘 수업 - 깊이 우선 탐색 1(실버 2) - Python 문제를 살펴보면 dfs(깊이 우선 탐색)을 구현하는 기본 문제이다dfs(깊이 우선 탐색)이란, 트리나 그래프를 탐색하는 기법 중 하나인데, 시작 노드에서 자식의 노드들을순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다 즉, 하나의 노드에서 3가지 갈래의 길이 있을 때하나의 갈래를 선택한 후에 다시 돌아와서 다른 노드를 선택하는 것이 아니라 선택한 노드에서 계속해서 깊게이루어진다는 것이다 그림판을 통해 설명을 하자면해당 그림의 경우 1번에서 2번으로 간 후에 3번으로 가는게 아니라(2-1-3) 2번에서 4번으로 이동하게 된다1번에서 2번을 탐색한 후에 3번을 탐색하는 것은 bfs(너비 우선 탐색)에 해당한다 해당 문제를 풀기 위한 간단한 의사코드도 존재한다 시작 정점에서 출발하여 깊이 우선 탐색으로.. 더보기
[Baekjoon]백준 3015 오아시스 재결합(플래티넘 5) - Python 문제를 살펴보면 서로 볼 수 있는 사람의 수를 구해야한다문제를 제대로 이해하기 위해 총 몇 쌍이 나오는지 직접 구해보았는데, (2, 4), (4, 1), (4, 2), (4, 2), (4, 5), (1, 2), (1, 2), (2, 2), (2, 5), (5, 1) 이렇게 총 10개이다(앞에서부터 정렬)즉, 마주보고 있는 사람도 포함하되, 중간에 위치한 사람의 키가 크지 않은 경우도 동시에 계산해야한다 스택을 1차원으로 해결해보려고 했는데 도저히 방법이 생각이 안 나서 찾아보았다검색을 해보니 2차원으로 사용하는 방법이 대부분이었고, 현재 키와 개수를 스택에 넣는 방법을 사용하였다stack에는 키와 해당 키의 개수를 저장하고, total_views에는 총 시야의 개수,cnt에는 같은 키를 가진 사람의 수를.. 더보기
[Baekjoon]백준 1725 히스토그램(플래티넘 5) - Python 이 문제는 이전에 풀었던 6549 히스토그램에서 가장 큰 직사각형와 굉장히 유사하다그래서 조금 고민해보다가 이전의 코드를 활용하며 다시 복습하는 느낌으로 코드를 작성하였다그러나, 해당 코드의 함수를 그대로 제출하였더니 틀렸습니다가 결과로 나왔다# 백준 6549 히스토그램에서 가장 큰 직사각형import sysdef sol(Rec): Rec.append(0) # 마지막 원소로 작은 값 0을 추가하여 스택이 비워지도록 도와줌 stack = [] max_area = 0 for i in range(len(Rec)): while stack and Rec[stack[-1]] > Rec[i]: # 스택의 최상단 높이보다 작은 경우 max_area 갱신 heigh.. 더보기
[Baekjoon]백준 9095 1, 2, 3 더하기(실버 3) - Python 문제를 살펴보면 문제 자체는 간단하다 어떠한 수를 완성하기 위해 가능한 경우의 수를 구하면 된다이 문제를 보자말자 들었던 생각으로는 나눠서 생각하면 더 간단하고, 그러면 동적 프로그래밍(dp)를 사용하면되겠다! 라는 생각이 들었다 그래서 어떠한 규칙이 존재하는지 확인해보았다dp[1] = 1  : 1dp[2] = 2 : 1+1, 2dp[3] = 4 : 1+1+1, 1+2, 2+1, 3 dp[4] = 7 : 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 dp[5] = 13 : 1+1+1+1+1, 1+2(2의 위치에 따라 달라지므로 총 5개), 2+2+1(같은 원리로 3개), 3+1+1(같은 원리로 3개), 3+2...가만히 보다보니 반복되는 규칙을 직관적으로 발견할 수 있었다.. 더보기

티스토리툴바