차곡차곡

https://www.acmicpc.net/problem/15686 아이디어치킨집의 개수 C개의 경우 C개의 치킨집 중 M개를 선택하는 모든 조합 : 1716개 조합각 조합에 대해 모든 집의 치킨 거리 계산(집의 개수 H, 치킨집 개수 M) : 최악의 경우 1300최악의 경우 O(1716⋅1300)≈2,230,800  즉 2.23×10^6 의 연산이 필요하기 때문에 브루투포스와 백트래킹을 활용해 모든 치킨집의 조합을 확인하며 계산하여 정답을 도출할 수 있다.  코드입력부N, M = map(int, input().split())city = [list(map(int, input().split())) for _ in range(N)]result = int(1e9)store = []house = []for i ..

https://www.acmicpc.net/problem/15591 문제 설명그래프와 유니온-파인드를 활용해 특정 조건을 만족하는 노드(동영상)들의 수를 구하는 문제이다. 그래프 구성동영상들은 노드, 동영상 쌍 간의 USADO 값은 간선의 가중치로 주어진다.총 N개의 노드와 N-1개의 간선이 있으며, 모든 노드는 하나의 연결 그래프를 이룬다. USADO 경로 계산: 두 노드 간의 USADO는 그들을 연결하는 경로의 간선 중 최솟값 아이디어처음 풀이로 BFS를 사용해 탐색했다. 하지만 시간초과가 발생했다. 따라서 union-find 를 사용해 해결했다. 또한 간선을 내림차순 정렬하여 K 이상의 간선만 처리하도록하여 효율성을 높였다. 코드노드 u가 속한 집합의 루트노드를 찾는 find 함수이다. 재귀함수를 ..

https://www.acmicpc.net/problem/7490 아이디어자연수 N이 3~9로 크지 않고, 연산자의 경우 +, -, 공백으로 3가지 경우가 포함된다.N에 대한 오름차순 수열에 대해 모든 연산자를 사용하는 경우를 뻗어나가며 수식의 결과가 0이면 체크하는 방식으로 코드를 구현했다. -> 브루트포스 알고리즘 파이썬 추가 아이디어 : eval처음에는 각 숫자를 계속 이어붙이며 연산을 수행했다. 하지만 이 로직을 리팩토링 할 수 있는 파이썬 내장팜수 eval을 알게되었다. eval 함수는 파이썬에서 제공하는 내장 함수로, 문자열로 표현된 식(expression)을 받아서 실행하고 그 결과를 반환한다. 사용법expr = "2 + 3 * (4 - 1)"result = eval(expr)print(re..

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 = ..

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팀의 큰 ..

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