본문 바로가기

알고리즘12

[node.js, 백준]16197 - 두 동전 목차 문제링크https://www.acmicpc.net/problem/16197문제N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.두 동전 중 하나만 보드에서 떨어뜨.. 2024. 6. 7.
[node.js, 백준]9663 - N-Queen 목차 문제링크https://www.acmicpc.net/problem/9663문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N  출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 주저리로직은 이해했으나 시간 초과가 일어나서 최적화하는데 애를먹었고 결국 최적화코드는 답을봐서 한번더 풀어야할 것같다. Queen을 N x N칸에 N개 배치할때 핵심은 한 줄에 하나씩 퀸이 꼭들어가야하는점을 생각해야했다.(경우의 수 줄이기) 그리고 반복문으로 해결하였는데 하나의 퀸을 배치하면 그 공격 대상에 다른 퀸이있는지 체크를 해줘서 .. 2024. 5. 21.
[node.js,백준]1987 - 알파벳 목차   문제링크https://www.acmicpc.net/problem/1987문제세로 𝑅$R$칸, 가로 𝐶$C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.입력첫째 줄에 𝑅$R$과 𝐶$C$가 빈칸을 사이에 두고 주어진다. (1≤𝑅,𝐶≤.. 2024. 5. 16.
[node.js,백준]11055 - 가장 큰 증가하는 부분 수열 목차   문제링크https://www.acmicpc.net/problem/11055문제수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.  주저리증가하는 부분수열중에서 그 값들을 비교해 가장.. 2024. 5. 10.
[node.js,백준]11057 - 오르막수 목차 문제링크https://www.acmicpc.net/problem/11057 문제오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.  출력 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.  주저리수는 0부터가능하기때문에 0~9까지 첫번째는 각 경우의 수는 1이다.이후로는 자기랑 같은수부터 높은수를 더해야하는데순서는 정렬이되어있는 상태.. 2024. 5. 9.
[Node.js,백준]1377 - 버블 소트 목차   문제 입력 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. 출력정답을출력한다.  풀이24년 3월 28일날 풀었으나 티스토리로 이관 정렬을 이용해서 푸는 문제 이다. 실제로 버블 정렬으로 풀면 시간 초과가 일어나기 때문에 다른 방법으로 풀어야 한다.버블정렬엔 어떠한 규칙이있는데 앞의수가 뒤의수보다 클때 ex)(10 > 5)앞의수는 뒤의수보다 작을때까지 어디든 이동이 가능하지만 뒤의 수는 앞으로 한번씩만 이동한다는 점이다.이 점을 이용하기 위해arrs라는 새로운 배열을 만들껀데 최초 배열의 [값, i(순서)]를 저장하고 값을 오름차.. 2024. 5. 8.
분할 정복 : 작은 부분에서 얻는 큰 지혜 안녕하세요! goodchuck 입니다!블로그에 방문해주셔서 감사합니다!  1. 분할 정복 알고리즘의 탄생 배경분할 정복 알고리즘은 1960년대 컴퓨터 과학자들이 복잡한 문제를 해결하기 위해 고안한 기법입니다. 당시 컴퓨터의 성능이 낮아서 큰 문제를 한 번에 해결하기 어려웠던 것이 계기가 되었습니다. 이에 문제를 작은 부분으로 나누어 각각 해결한 뒤, 그 결과를 합치는 방식으로 접근하게 되었습니다.  2. 분할 정복 알고리즘이란?분할 정복 알고리즘은 큰 문제를 작은 부분 문제로 나누어 각각을 해결한 다음, 그 해답을 모아서 전체 문제를 해결하는 알고리즘 설계 패러다임입니다. 이 기법은 재귀적인 방식으로 동작하며, 높은 효율성을 가지고 있습니다.  3. 분할 정복 알고리즘의 일반적인 절차1. **분할(Div.. 2024. 5. 6.
알고리즘의 브루트포스(Brute Force): 모든 경우를 탐색하는 간단한 방법 안녕하세요! goodchuck 입니다!블로그에 방문해주셔서 감사합니다!   브루트포스의 개념 브루트포스(Brute Force)는 모든 가능한 경우를 일일이 탐색하여 원하는 결과를 얻는 알고리즘입니다. 이 방법은 간단하지만, 경우의 수가 많을 경우에는 효율적이지 않을 수 있습니다. 하지만 경우의 수가 적거나 작은 경우에는 쉽게 구현할 수 있고, 올바른 답을 보장합니다.  브루트포스의 동작 원리 브루트포스는 다음과 같은 과정을 거쳐서 동작합니다:1. 가능한 모든 경우의 수를 생성합니다.2. 각 경우의 수에 대해 조건을 확인하여 올바른 답을 찾습니다.  브루트포스의 장단점 **장점:**- 구현이 간단하고 직관적입니다.- 모든 가능한 경우를 탐색하므로 정확한 결과를 얻을 수 있습니다. **단점:**- 경우의 수.. 2024. 5. 6.
알고리즘의 BFS(Breadth-First Search): 그래프 탐색의 기본 안녕하세요! goodchuck 입니다!블로그에 방문해주셔서 감사합니다! BFS의 등장 배경 BFS(Breadth-First Search)는 그래프를 탐색하는 알고리즘 중 하나로, 너비를 우선하여 탐색하는 방법입니다. 이 알고리즘은 최단 경로를 찾거나 네트워크에서 연결된 모든 노드를 탐색하는 등 다양한 문제를 해결하는 데 사용됩니다. 예를 들어, 소셜 네트워크에서 특정 사용자와 다른 모든 사용자 간의 관계를 찾거나, 게임 개발에서 유닛의 이동 경로를 계산하는 등의 문제를 해결할 때 BFS가 유용하게 사용됩니다.  BFS의 개념 BFS는 다음과 같은 과정을 거쳐서 동작합니다:1. 시작 노드를 큐(Queue)에 넣고, 이 노드를 방문한 것으로 표시합니다.2. 큐에서 노드를 꺼내어 방문합니다.3. 방문한 노드와.. 2024. 5. 6.
알고리즘의 Deque: 양쪽 끝에서 삽입 및 삭제가 가능한 자료구조 안녕하세요! goodchuck 입니다!블로그에 방문해주셔서 감사합니다!  Deque의 개념 Deque(덱)는 양쪽 끝에서 삽입 및 삭제가 가능한 자료구조로, Double-ended Queue의 줄임말입니다. Deque는 스택과 큐를 합친 자료구조로, 스택의 후입선출(LIFO, Last-In-First-Out)과 큐의 선입선출(FIFO, First-In-First-Out)을 모두 지원합니다.  Deque의 등장 이유 Deque는 다음과 같은 상황에서 사용됩니다:- 덱블록: 컴퓨터의 파일 시스템에서 데이터를 저장하는 데 사용되는 블록의 한 유형으로, 양쪽 끝에서 데이터를 추가하거나 제거할 수 있습니다.- 실시간 데이터 처리: 데이터를 수집하고 처리하는 동안 양쪽 끝에서 삽입 및 삭제를 효율적으로 수행해야 할.. 2024. 5. 6.