99클럽 코테 스터디 12일차 TIL - BFS의 '동시' 탐색

문제https://www.acmicpc.net/problem/7569오늘의 학습 키워드BFS 탐색으로 서로 다른 좌표에서 '동시에'  탐색이 처리된다는 것의 의미는 무엇일까?공부한 내용 본인의 언어로 정리하기해결 과정문제의 핵심은 서로 다른 공간에 있는 익은 토마토들이 주변의 토마토들에 영향을 주며 하루씩 익어 가는 것을 어떻게 코드로 구현하냐는 것이라고 생각한다. 문제의 풀이법이 BFS로 접근해야 한다는 것은 쉽게 떠올릴 수 있었는데 익은 토마토들이 '동시에' 주변의 안 익은 토마토에 영향을 주게끔 코드를 구현하는 방법을 잘 떠올리지 못했다. 그래서 처음에는 days라는 3차원 배열을 만들고 각각의 익은 토마토에 대해 bfs를 실시하며 익는데까지 걸린 날을 갱신해주는 코드로 구현했다. 먼저 days라는..

• format_list_bulleted 코딩테스트
• · 2024. 11. 10.
• textsms

[99클럽 코테 스터디 7일차 TIL] 프로그래머스 모음사전

문제https://school.programmers.co.kr/learn/courses/30/lessons/84512오늘의 학습 키워드중첩 for문과 DFS와의 관계공부한 내용 본인의 언어로 정리하기원래 처음엔 아주 허접하게 문제를 풀었다. 바로 중첩 for문을 이용했다. 참으로 무식한 방법을 사용했다.모음이 5개이니 5개의 for문을 이용해 단어 목록을 만들고 단어 목록에서 주어진 단어의 인덱스를 반환했다.class Solution { static String[] arr = new String[]{"A", "E", "I", "O", "U"}; public int solution(String word) { List map = new ArrayList(); for (in..

• format_list_bulleted 코딩테스트
• · 2024. 11. 3.
• textsms

99클럽 코테 스터디 4일차 TIL [DFS]

문제https://www.acmicpc.net/problem/24479오늘의 학습 키워드인접행렬과 인접리스트공부한 내용 본인의 언어로 정리하기1. DFS (Depth-First Search)DFS는 깊이 우선 탐색으로, 그래프나 트리의 한 노드에서 시작해 가능한 깊이까지 탐색한 뒤 다시 돌아와 다른 경로를 탐색하는 방식이다. 주요 단계는 다음과 같다.방문: 시작 노드를 방문하고 표시.재귀 또는 스택 이용: 현재 노드에서 갈 수 있는 깊이까지 이동.백트래킹: 더 이상 이동할 수 없을 때, 이전 경로로 돌아가면서 탐색.DFS는 스택을 이용해 구현할 수 있고, 재귀 함수로도 구현할 수 있다. 2. 스택을 이용한 DFS (반복문 방식)장점:메모리 효율적: 재귀 깊이가 깊어지면 호출 스택이 커져 메모리 부족 현상..

• format_list_bulleted 코딩테스트
• · 2024. 11. 1.
• textsms

[99클럽 코테 스터디 2일차 TIL] 백준 11561 이진탐색, 등차수열

문제https://www.acmicpc.net/problem/11561오늘의 학습 키워드등차수열이번 문제에서 등차수열이라는 점을 인식하는게 매우 중요했다.잘 생각해보면, 두번째 규칙에 의해 두번째 점프부터는 이전 점프 길이보다 1이상 점프해야하고 우리는 밟을 수 있는 최대 징검다리 수를 생각해야하므로 이전 점프보다 1보다 크게 점프하면 된다. 즉 초항은 처음 점프 길이, 공차가 1인 등차수열로 점프한 길이의 수열을 생각해볼 수 있다. 처음 점프 길이가 1이면 두번째는 2, 세번째는 3 ... 으로 이어진다.중요한 건 등차수열의 합이다. 왜 중요하냐면 총 점프한 길이가, 즉 등차수열의 합이 N을 초과하지 않는 조건에서 최대로 밟을 수 있는 징검다리의 수를 구해야하기 때문이다. 공차가 1이고 점프한 횟수를 ..

• format_list_bulleted 코딩테스트
• · 2024. 10. 30.
• textsms