'알고리즘' 카테고리의 글 목록 (2 Page)

[CodeTree] 루돌프의 반란 - Java

2024.04.06

✨ 구현 ➡︎ 연쇄적으로 이동시키기 & 이동한 좌표 갱신하고 잘 반영시키기 https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 📍고려해야할 점 산타가 가까운 루돌프에게 이동할 때, 반대로 루돌프가 가까운 산타에게 이동할 때 어느 방향으로 이동할지 결정하기 위해서는 거리 공식 계산을 이용해서 비교해야 한다. 👉 루돌프의 경우 8방향 이동 가능하고, 산타는..

알고리즘/🗂️ 정리

🐌 달팽이 이동 효율적인 코드 🐌

2024.03.30

달팽이 이동을 효율적으로 작성한 코드가 있어서 기록한다. 우선 격자의 한 변은 무조건 홀수다. 안 -> 밖으로 이동하는 방향과 밖 -> 안으로 이동하는 방향을 한 번에 저장하는 로직이다. 규칙 찾기 달팽이 이동하는 규칙을 찾아보면 현재 방향이 만약 위 또는 아래일 때마다 이동하는 횟수가 1씩 증가한다. 안 ➔ 밖으로 이동하는 경우를 보면, ⬆︎ ➡︎ 로 이동할 때는 1, 3, 5 ... 칸씩 이동하고, ⬇︎ ⬅︎ 로 이동할 때는 2, 4, 6 ... 칸씩 이동한다. (0, 0)칸으로 향해 가는 마지막 ⬆︎는 짝수 칸만큼 이동하지만 어차피 (0, 0)에서 끝나기 때문에 break하면 된다. 밖 ➔ 안으로 이동하는 달팽이 모양은 위와 반대로 생각하면 되기 때문에 방향만 바꿔주면 된다. 코드 public st..

알고리즘/CodeTree

[CodeTree] 싸움땅 - Java

2024.03.24

✨ 구현 https://www.codetree.ai/training-field/frequent-problems/problems/battle-ground/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 📍 고려해야할 점 해당하는 칸에 있는 총들을 비교하고 가장 공격력이 높은 총을 선택해야한다. 진 사람의 경우 총을 해당하는 칸에 두고, 조건에 따라 이동한다. 🕹️ 알고리즘 과정 진 사람이 총을 버리고 이동해야하는데, 버리는 코드를 작성하지 않아 디버깅하는데 시간을 생각보다 많이 쏟은 것 외에는 딱히..

알고리즘/BOJ

[BOJ] 17837 새로운 게임2 - Java

2024.03.19

✨ 구현 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 📍 고려해야할 점 한 좌표 안에 여러 개의 말이 들어갈 수 있다. ➔ 이동하려는 칸에 말이 존재한다면 그 위에 말이 올라감 한 말이 이동할 때 위에 올려져 있는 말까지 모두 이동한다. 여러 개의 말이 들어갈 때 좌표의 색깔에 따라 정렬 기준이 존재한다. 좌표의 범위를 벗어나거나 좌표 칸이 파란색일 때의 조건을 유의해야한다. 🕹️ 풀이과정 어떤 자료구조로 활용할지 정하기만 하면 쉽게 풀..

알고리즘/BOJ

[BOJ] 17485 진우의 달 여행 (Large) - Java

2024.03.12

✨ DP https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 📍 고려해야할 점 왼쪽 대각선, 아래, 오른쪽 대각선 3가지 방향으로 이동한다. ✨✨ 같은 방향으로 두 번 연속으로 움직일 수 없다. ✨✨ 🕹️ 문제 풀이 현재 위치를 기준으로 그 전 단계에 사용했던 연료의 양을 계속 알고 있어야 한다. 그 전 단계에 사용했던 연료의 양과 현재 위치에 있는 연료의 양의 합을 구해서 최소의 연료를 사용할 수 있는 경우..

알고리즘/🗂️ 정리

LCS (최장 공통 부분 수열)

2024.03.11

코테 보다가 나온 것이기에 정리한다... LCS (Longest Common Subsequence)는 주어진 여러 개의 수열 중에서 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 것이다. 예시를 보자면, ACAYKP의 부분수열은 {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, {A, Y}, ... {A, C, A, Y, K, P} 이고, CAPCAK의 부분수열은 {C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, {C, C}, ... {C, A, P, C, A, K}이 있는데 각각의 부분수열 중에서 서로 같은 부분수열이 있을 것이다. 그중 가장 긴 것을 찾으면 되는데 위의 예시의 답은 길이가 4인 {A, C, A, K} 이다. 대표적..

알고리즘/프로그래머스

[프로그래머스] 단어 변환

2024.03.06

✨ BFS/DFS https://school.programmers.co.kr/learn/courses/30/lessons/43163# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📍 고려해야할 점 한 번에 한 개의 알파벳만 변경 가능 begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 굳이 배열의 순서대로 찾을 필요 없음 🕹️ 풀이과정 👉 이 문제 같은 경우 DFS와 BFS 모두 풀이 가능하다. 하지만 DFS로 구현할 시에는 시간복잡도가 크다. 🔹 DFS words 배열에서 현재 단어와 한 글자만 다른 단어를 탐색한다. 👉 중복 탐색을 방..

알고리즘/BOJ

[BOJ] 20058 마법사 상어와 파이어스톰 - Java

2024.03.01

✨ BFS + 구현 ➔ 부분 격자를 시계방향으로 90도 회전 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 📍 고려해야할 점 2^L * 2^L 크기의 부분 격자로 나누고 모든 부분 격자를 시계방향으로 90도 회전 L=1일 때, 2x2의 부분격자가 시계방향으로 90도 회전 L=2일 때, 4x4의 부분격자가 시계방향으로 90도 회전 (x, y)칸에서 인접한 칸(상하좌우) 중 얼음이 있는 칸이 3개 미만이면 (x, y)칸 얼음의..

티스토리툴바