차곡차곡

https://www.acmicpc.net/problem/14502 아이디어연구소의 최대 크기가 크지 않기 때문에 벽을 세우는 모든 경우의 수를 파이썬의 combination(조합)을 이용해 탐색하면된다.입력받은 연구소에서 빈칸의 좌표와 바이러스의 좌표를 각각 저장한다.빈칸의 좌표 중에서 Combinations를 사용하여 3개를 조합해 탐색한다.해당 조합의 좌표에 벽을 세우고 바이러스를 최대로 확장한다.연구소의 남은 안전구역을 계산한다.남은 안전구역이 최대가 되는 값을 출력한다. 바이러스 확산이때 연구소의 바이러스를 확장할 때에는 BFS를 사용하여 확장하였다.def bfs(temp_graph): q = deque(virus_positions) while q: x, y = q.po..

https://www.acmicpc.net/problem/9663 해당 풀이는 Python 으로 제출시에도 시간초과가 발생하지 않습니다. 초기 아이디어처음에 문제를 풀 때는 2차원 배열을 사용하여 체스판을 표현한 후, 백트래킹을 이용해 각 칸에 퀸을 배치했다. 결과는 당연히 시간초과가 발생했다.N이 커질수록 백트래킹을 통해 모든 가능성을 탐색하는 과정에서 시간 복잡도가 급격히 증가하기 때문이다. 이를 해결하기 위해서 퀸의 이동 방식에 대해서 다시 생각해보면 아래와 같다. 퀸의  이동방식 퀸은 다음과 같은 방식으로 이동한다. 같은 행에 있는 퀸끼리는 서로 공격할 수 없으므로, 한 행에 하나의 퀸만 배치할 수 있다.퀸은 같은 열에 있는 다른 퀸과도 공격할 수 없으므로, 한 열에도 퀸은 하나만 배치되어야 한다..

https://www.acmicpc.net/problem/1743 문제를 보고 바로 BFS를 이용해 상하좌우에 이어진 쓰래기를 탐색해 최대(Max)를 구하면되겠다고 생각했다. 처음 코드 (메모리 초과)from collections import dequeimport sysinput = sys.stdin.readlinedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]result = 0n, m, k = map(int, input().split())trash = [[False]*m for _ in range(n)]for _ in range(k): x, y =map(int, input().split()) trash[x-1][y-1] = Truedef bfs(x, y): cnt = ..

탐색이란? 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 둘을 이해하기 위해서는 기본 자려구조인 스택과 큐에 대한 이해가 되어야 한다. 자료구조란? 자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(push) : 데이터를 삽입한다. 삭제(pop) : 데이터를 삭제한다. 추가로 스택과 큐를 사용할 때에는 언더플로(underflow)와 오버플로(overflow)를 고려해야한다. 오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 반면 특정한 자료구조에..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 장르별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려고한다. 노래는 고유 번호로 구분되며 노래를 수록하는 기준은 아래와 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래 장르를 나타내는 문자열 배열 gen..

https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 아파트 N개가 주어지고 아파트 옥상에 기지국이 설치되어있다. 해당 기지국의 범위가 w로 변경되면서 기지국을 추가로 설치해야하는데, 이때 최소로 설치하는 기지국의 개수를 return해줘야한다. 기지국 설치 아파트기준으로 양쪽으로 w만큼 전달 할 수 있다. ex_) 만약 4번 아파트에 w가 2라면 2,3,4,5,6 번의 아파트를 해당 기지국으로 커버할 수 있다. 접근법 모든..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 고속도로를 이용하는 차량들의 경로 routes가 주어진다. routes안에는 차량이 고속도로를 진입하는 지점, 나간 지점이 적혀있다. i 번 째 차량은 routes[i][0]에 고속도로에 들어오고 routes[i][1]에 고속도로에서 나간다. 고속도로를 이용하는 모든 차량이 적어도 한번은 단속 카메라를 만나게 하기 위해서 카메라를 최소 몇대 설치해야하는지 return 한..

https://school.programmers.co.kr/learn/courses/30/lessons/12987?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 각 팀원이 숫자를 가지고 있고 상대 팀 팀원과 만나 숫자를 비교했을 때 더 큰 숫자를 내면 승점을 얻는다. 만약 숫자가 같으면 둘다 승점을 얻지 못한다. A팀의 팀원의 숫자와 출선 순서가 공개 되었을 때 B팀이 얻을 수 있는 최대 승점을 return 해야한다. 접근법 A팀 팀원이 낸 숫자보다 B팀에서 낼 수 있는 숫자가 작은 경우 B팀의 큰 ..

그리디 알고리즘 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 탐욕법이라고도 불리는데 이름에서 알 수 있듯이 단순 무식하게, 탐욕적(현재 상황에서 지금 당장 좋은 것만 고르는 것)으로 문제를 해결하는 알고리즘이다. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 대체로 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘 적용 조건 탐욕적 선택 속성 : 앞의 선택이 이후의 선택이 영향을 주지 않는다. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 그리디(탐욕) 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있..

복잡도란? 복잡도 (Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 크게 두가지로 구분할 수 있다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 시간복잡도와 공간복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 시간적 이점을 얻을 수 있는 경우가 있는데 이 방법으로 메모이제이션 기법이 있다. 시간 복잡도 시간 복잡도를 표기할 때는 빅오..