알고리즘/백준(30)
-
백준 2407 c++(파스칼 삼각형) / python(factorial)
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 맨 처음에는 생각을 하지 않고, 그냥 queue에 값을 넣고, 큰 수가 나오면 에라토스테네스의 체를 통해 곱하는 값에 대해서 조정하면 되지 않을까?라는 생각으로 접근했다. 이렇게 생각없이 접근하면 헛고생만 합니다.. 꼭 문제 풀기 전에 범위 벗어나는지 확인해야 합니다... 문제에서 나올 수 있는 값에 최댓값에 전혀 미치지 못하는 long long int의 범위이다.. 그러면 어떻게 풀면 될까? 이런 문제는 거의 다 문자열로 풀이가 가능하다. 아래는 22%에서 터지는 코드인데 왜 터질까? #include #incl..
2023.04.10 -
백준 16236 아기상어 c++
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 엄청난 시도 후 전장에서 승리하고 글을 작성합니다. 아기상어의 크기보다 작은 것만 섭취가능 아기상어의 위치는 9로 나타냄 아기상어의 크기만큼 섭취를 한다면, 크기가 1 커진다. bfs로 작은게 있는지 판단 -> 판단 후 있다면 상하좌우 위치 가중치 while (true) { if (hunt(k)) { continue; } else { break; } } 메인 알고리즘은 hunt에서 fals..
2023.04.08 -
백준 뱀과 사다리 게임 16928 ( c++ )
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제를 읽고 사다리만 타면 되지 않을까?라는 생각을 했었는데 좋은 사다리 위치로 가기까지 뱀의 도움도 필요하다는 것을 느끼고, 바로 BFS로 들어갔다. Queue에 향하는 위치, 움직인 횟수를 저장하는 두 개의 변수가 필요하다고 생각함. 원래는 pair int int를 사용해도 좋지만, 나는 구조체를 더 선호하는 편이다. 그래서 구조체를 사용해서 qu..
2023.04.07 -
백준 10026 적록색약(C++)
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net Solution 1. 문제를 보자 느낀 점 DFS로 풀면 되겠다.. 토마토 문제랑 비슷하다.. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마..
2023.04.06 -
[백준] 10988 python 팰린드롬인지 확인하기 (3가지 방법)
1. 문자열 슬라이싱(slicing)을 이용하는 방법 s = input() if s == s[::-1]: print(1) else: print(0) 2. 반복문(for/while)을 이용하는 방법 s = input() n = len(s) flag = 1 for i in range(n//2): if s[i] != s[n-i-1]: flag = 0 break print(flag) 3. 내장함수 reversed 사용 s = input() if list(s) == list(reversed(s)): print(1) else: print(0) https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100..
2023.01.25 -
[백준] 7662 이중 우선순위 큐
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. I 일때 값을 넣어주고, 들어왔음을 확인시켜준다. 2. D일때는 값에다가 들어왔음을 표시해주고 최대값, 최소값에 맞게 POP해준다. 3. 출력은 들어왔음을 표시해준것은 다 pop을 해주고 top값에 있는 값을 출력하준다. #include #include #include #include #include #include using namespace std; bool visited[100000..
2022.07.11