본문 바로가기

cpp32

[백준] 1504번 특정한 최단 경로 : 다익스트라 - C++ 1504번 특정한 최단 경로 노드 n개가 주어질 때 시작점에서 v1, v2를 모두 경유하여 끝점으로 가는 최단경로를 구하는 문제입니다. 가능한 경우의 수는 두 가지뿐입니다. 첫 번째, 시작점 - v1 - v2 - 끝점. 두 번째, 시작점 - v2 - v1 - 끝점. 두 경로중 거리가 더 짧은 경로를 출력하면 됩니다. 시작점에서 v1, v2까지의 최단거리와 v1, v2사이의 최단거리, v1, v2에서 끝점사이의 최단거리를 구하면 됩니다.풀이방법 처음에는 학교에서 배운 다익스트라를 그대로 적용하여 distance배열을 업데이트 하는 방식을 사용했습니다. 하지만 distance배열에서 최솟값을 찾고 업데이트를 하는 과정이 오래 걸려 시간초과가 발생했습니다.// 시간초과 코드#include #include us.. 2024. 11. 18.
[백준] 14500번 테트로미노 - C++ 테트로미노 N x M 크기의 보드에 정사각형 4개로 이루어진 블록을 무작위로 배치했을 때 블록에 가려진 정수의 합이 가장 큰 경우의 값을 찾는 문제입니다. 어떻게 풀어야 하나.. 고민하다가 아이디어가 당장 안 떠올라서 노가다 - 멋있는 말로 브루트 포스 - 로 풀었습니다.풀이방법 그림과 같이 엑셀에 모든 블록의 경우의 수를 정리해 보니까 19가지의 블록을 최대 500 x 500의 보드에 배치하는 것이기 때문에 시간제한 2초 안에 성공할 수 있을 것 같아서 브루트포스를 선택했습니다. 그림과 같이 블록들을 가로 x 세로의 크기대로 분류하면 총 5가지의 유형으로 분류할 수 있습니다. 유형별로 2중 for문을 돌리고 for문 안에서 공통된 블록은 한 번만 계산함으로써 최대한 연산을 줄였습니다.코드#include.. 2024. 11. 9.
[백준] 7576번 토마토 - C++ 토마토 위 그림과 같은 상자에 한 칸에 하나씩 토마토가 들어있고 익은 토마토는 하루 만에 인접한 토마토를 익게 만든다고 했을 때 모든 토마토가 익는데 걸리는 일수를 구하는 문제입니다.입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.토마토가 하나 이상 있는 경우만 .. 2024. 11. 4.
[백준] 1074번 Z - C++ Z 위 그림과 같이 주어진 보드를 z모양으로 순회할 때 r행 c열에는 몇 번째로 방문하는지 출력하는 문제입니다. 행, 열 번호와 방문 순서는 모두 0부터 시작합니다.입력첫째 줄에 정수 N, r, c가 주어진다.출력r행 c열을 몇 번째로 방문했는지 출력한다.제한1 0 예제 입력2 3 1예제 출력11풀이 방법1. 현재 보드를 좌상단의 좌표x, y와 보드의 size로 표현한다. size=2^z2. count = 03. 현재 보드에서 c, r의 위치가 좌상단, 좌하단, 우상단, 우하단 중 어디인지 알아낸다.4. n>1일 경우, 위치에 따라 count변수에 0, size*size/2, size*size/4, size*size/4*3을 더한다.5. n=1일 경우, 위치에 따라 count변수에 0, 2, 1, 3을 .. 2024. 11. 3.
[백준] 5525번 IOIOI - C++ IOIOIP(N) : P(1) = "IOI", P(2) = "IOIOI", P(3) = "IOIOIOI",... 일 때 주어진 문자열 S에 P(N)이 몇 군데 포함되어 있는지 출력하는 문제입니다.입력첫째 줄에 N, 둘째 줄에 S의 길이 M, 셋째 줄에 S가 주어진다.출력S에 P(N)이 몇 군데 포함되어 있는지 출력한다. (P(N) 끼리 겹칠 수 있음)알고리즘// KMP 알고리즘을 응용했다.while(i=0;i코드#include #include using namespace std;int main() { int n, m, cnt = 0; string s; cin >> n >> m >> s; int cmp_len = 1 + 2 * n; bool prev_cmp = false; for (int i = 0; i .. 2024. 10. 21.
[코테] 해시 해시해시 함수해시함수는 특정한 Key를 입력받으면 적절한 해시값(Index)을 반환하는 함수이다. 해시 함수를 이용하면 인덱스에 키 정보를 저장할 수 있다. 키를 입력받으면 해시 함수를 적용하여 인덱스를 바로 구하고 인덱스로 접근하면 O(1) 시간에 값을 얻을 수 있다.해시함수는 KEY의 개수가 n개 라면 해시값은 0 ~ n-1 사이 값을 내야한다. 이때 KEY값에 따라 동일한 해시값이 나올 수 도있는데 이것을 해시충돌이라고 한다. 이러한 해시충돌이 적을수록 좋은 해시함수라고 할 수 있다.해시 함수 - 나눗셈 법h(x) = x mod k (x는 키, k는 소수)k로 나눈 나머지는 무조건 0 ~ k - 1이기 때문에 해시 함수라고 할 수 있다. (k가 클수록 충돌이 적음)해시 함수 - 곱셈 법h(x) = .. 2024. 10. 19.

티스토리툴바