본문 바로가기

Algorithm & SQL

 (145)
[Algorithm] [Python] 백준/BOJ - 3190 _ 뱀 3190 - 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길..
[Algorithm] Dynamic Programming - 동적 계획법 Dynamic Programming - 동적 계획법 DP, 동적계획법이란? 큰 문제를 작은 문제로 나누어 접근하는 방식의 문제를 일컫는 용어입니다. 어떠한 문제를 나누어 접근한다는 시각에서는 분할정복(Divide and Conquer) 와 컨셉이 비슷합니다. 하지만 나누어 접근하는 작은 문제가 중복해서 일어나는가에 대한 여부에 차이가 존재합니다. 분할정복은 작은 문제에서 반복이 일어나지 않습니다. 반면 DP는 작은 부분의 문제들이 반복되는 컨셉을 이용해 문제를 풀어나가는 방법입니다. Memoization 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 다시 사용하는 방법으로 동적계획법에 핵심이 되는 기술입니다. Memoization은 동적 프로그래밍 방식이 작은 문..
[Algorithm] DFS&BFS - 깊이 우선 탐색, 너비 우선 탐색 (그래프 탐색) DFS & BFS - 그래프 탐색 인접 리스트와 인접 행렬의 차이 인접 행렬 방식은 노드 간 모든 관계를 저장하므로 노드가 많을수록 많은 메모리가 불필요하게 낭비됩니다. 반면, 인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리를 보다 효율적으로 사용하게 됩니다. 하지만 인접 리스트 방식에 비해 특정 두 노드가 연결되어 있는지 바로바로 확인이 불가하기 때문에 정보를 얻는 속도가 느려집니다. DFS DFS의 동작 방식에 대해 알아보겠습니다. DFS는 깊이 우선 탐색 이라는 이름대로 특정 경로를 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 이후, 다시 돌아가서 다른 경로를 탐색하는 알고리즘입니다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 아래와 같습니다. 탐색 시작 노드..
[Algorithm] [Python&Swift] BOJ/백준 - 1439 _ 뒤집기 1439 - 뒤집기 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력..
[Algorithm] Greedy - 탐욕법 Greedy - 탐욕법 그리디 알고리즘은 매우 단순하면서 강력한 방법이다. 알고리즘의 흐름을 보면 왜 "greedy" 라는 이름이 붙었는지 알 수 있다. 그리디 알고리즘은 현재 상황에서 가장 좋은 최적의 해만 고르는 방법이다. 즉, 매 순간 제일 최적의 해로 보이는 해를 선택하며 현재의 선택이 나중에 어떠한 영향을 미칠지는 고려하지 않는다. 따라서 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 최적의 해만 선택해도 문제를 정상적으로 풀어낼 수 있는지 파악해야 한다. -> 그리디의 핵심! 예제 풀이 1. 백준 - 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다..
[Algorithm] [Python] BOJ/백준 - 11403 _ 경로 찾기 11403 - 경로 찾기 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 제출 코드 from sys import stdin from collection..
[Algorithm] [Python&Swift] Programmers - 네트워크 프로그래머스 - 네트워크 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 ..
[Algorithm] [Python] 백준/BOJ - 1946 _ 신입 사원 1946 - 신입사원 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성..

티스토리툴바