생각하는 아져씨

https://school.programmers.co.kr/learn/courses/30/lessons/42840문제 정의수포자는 어떤 패턴으로 정답을 찍는데 3명의 수포자 중 정답을 가장 많이 맞힌 사람이 누구인지 출력하는 문제이다. 접근 방법시험 문제가 최대 10,000문제로 완전 탐색을 해도 시간 초과는 걱정 없을 것 같아서 완전 탐색으로 접근했다. 문제 해설1번, 2번, 3번의 수포자의 찍기 패턴을 정의한다.1번부터 주어진 answers의 길이까지 1번, 2번, 3번이 정답을 맞췄는지 확인한다.1,2,3번의 패턴의 길이는 다르기때문에 각 패턴의 길이만큼 나눠주면 순서를 반복할 수 있다.즉, 1번 수포자의 6번 답은 6 & len(1번 패턴 길이) 로 접근할 수 있다. 풀이# 시험 최대 10,000..

4485번: 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485문제 정의주인공 링크는 현재 도둑루피가 가득한 N*N 크기의 동굴안에 젤 안쪽에 있다. ([0][0]에 위치)동굴의 반대편으로 가야하는데, 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃게된다.한번에 상하좌우 1칸씩 이동할 수 있다.이 때 잃는 금액을 최소로 하여 동굴을 이동하려고 한다. 링크가 잃을 수 밖에 없는 최소 금액을 구하면 된다. 접근 방법‘잃을 수 밖에 없는 최소 금액’ = 동굴의 마지막 [N-1][N-1] 로 가는데 드는 비용을 최소화하는 경로로 가야한다.따라서 최단경로, 다익스트라로 풀 수 있다.다익스트라는 노드와 간선의 정보가 있어야 하는데, 이 문제에서는 다음과 같다.노드: 도둑루..

다익스트라(Dijkstra)다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점 → 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선은 포함할 수 없다. (현실세계에 사용하기 매우 적합한 알고리즘 중 하나이다.) 👉 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는?최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제가 큰 문제의 부분집합에 속해있다. 👉 그리디 알고리즘의 일종인 이유는?매번 ‘가장 비용이 적은 노드’를 선택하기 때문이다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다음의 그래프에서 노드 1에서 2,3,4 ..

개요누적합누적합 예제 문제 살펴보기2차원 배열에서 누적합구현간단한 구현 예제구현 시 고려해야 할 메모리 제약 사항 (Python)채점 환경 (Python)문제를 푸는 방법참조 개요오늘은 알고리즘의 가장 첫번째인 누적합과 구현에 대해서 공부한다. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다. 공부를 할 때 마다 새로운 지식을 계속해서 정리할 예정이다.누적합누적합이란 요소들의 누적한 합을 의미한다.어떤 배열을 기반으로 앞에서 부터 요소들의 누적한 합을 저장해서 새로운 배열을 만들고 이를 활용하는 방식이다. 누적합의 종류에는prefix sum: 앞에서부터 더하는 것 → 코딩테스트에 나오는 것suffix sum: 뒤에서부터 ..

개요시간복잡도시간 복잡도란?빅오표기법(Big-O notation) 빅오표기법빅오 표기법 복잡도 비교상수시간 시간복잡도는 O(1)문제로 연습하는 시간복잡도시간복잡도의 존재 이유는 효율적인 코드의 척도!자료구조의 시간복잡도공간복잡도공간복잡도공간복잡도 계산공간복잡도를 참고한 문제 풀이 방법참조 개요알고리즘을 해결할 때는 복잡도가 굉장히 중요하다. 복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 하나씩 공부해보도록 하자. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다.시간복잡도시간 복잡도란?입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복횟수를 중점으로 측정된다. 👉 시간복잡도는 시간을 재야할까?아..

1446번: 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 문제 정의 모든 지름길은 일방통행이고 고속도로 역주행 금지이다. (고속도로 길이를 넘어서 다시 뒤로 갈 수 없음.) 지름길의 정보가 주어졌을 때, 세준이가 운전해야 하는 거리(길이)의 최솟값을 구하면 된다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 접근 방법 처음에 지름길을 많이 사용할 수록 좋다고 판단하여 지름길 정보를 순회하며 거리의 합을 비교하고 최소 거리를 출력하고자했다. 그래서 구현이..