너비 우선 탐색 (BFS, Breadth-First Search) BFS는 그래프의 모든 정점을 탐색하는 알고리즘 가장 가까운 정점부터 우선적으로 탐색하는 방식 특징 재귀적으로 동작하지 않는다 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 (무한 루프의 위험) 방문한 노드들을 차례대로 저장 한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다 Prim 알고리즘, 다익스트라 알고리즘(Dijkstra’s Algorithm) 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 큐에 추가: 현재 정점에 인접한 모든 정점을 큐에 추가합니다. 큐에서 정점 추출: 큐에서 정점을 하나씩 추출하며 탐색합니다. 방문..
알고리즘
Programmers_등산 코스 정하기 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다. 예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다. 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 inte..
문제 설명 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다. 모든 달은 28일까지 있다고 가정합니다. 다음은 오늘 날짜가 2022.05.19일 ..
Programmers_코딩 테스트 공부 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다. A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다. B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문..
문제 나만의 카카오 성격 유형 검사지를 만들려고 합니다. 성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다. 지표 번호 성격 유형 1번 지표 라이언형®, 튜브형(T) 2번 지표 콘형©, 프로도형(F) 3번 지표 제이지형(J), 무지형(M) 4번 지표 어피치형(A), 네오형(N) 4개의 지표가 있으므로 성격 유형은 총 16(=2 x 2 x 2 x 2)가지가 나올 수 있습니다. 예를 들어, "RFMN"이나 "TCMA"와 같은 성격 유형이 있습니다. 검사지에는 총 n개의 질문이 있고, 각 질문에는 아래와 같은 7개의 선택지가 있습니다. 매우 비동의 비동의 약간 비동의 모르겠음 약간 동의 동의 매우 동의 각 질문은 1가지 지표로 성격 유형 점수..
문제 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import jav..
결론을 먼저 말하자면, 배열과 리스트 간의 성능 차이는 사용 사례와 구현에 따라 다를 수 있으며, 종종 미미 할 수 있다 하지만, 자료구조 관점에서 리스트와 배열의 차이를 파악해보자 Intro. 궁금하더라 원래는 파이썬으로 알고리즘 문제를 풀었었는데, 자바로 풀게 되면서 궁금함을 느꼈다 이런 기초가 재밌더라 왠지 계속 글을 수정해 나가야겠다 실습 1. 데이터 읽기와 저장 비교 배열 쓰기 시간: 29.30 ms 리스트 쓰기 시간: 64.75 ms 배열 읽기 시간: 0.00 ms 리스트 읽기 시간: 0.01 ms 배열 쓰기 배열의 크기는 고정되어 있으므로, 쓰기 연산은 매우 빠릅니다. 리스트 쓰기 ArrayList는 동적으로 크기를 조정할 수 있으므로, 필요에 따라 내부 배열을 확장해야 할 수도 있습니다. ..
MOC: Index: 🏷️ Develop Notes 풀이 최종적으로는 하얀 블록과 파란 블록의 갯수를 찾으면 되는 문제이다 분할 정복법과 재귀가 이번 문제의 핵심이다 알고리즘을 못 떠올려서 for문을 여러 개 만드는 삽질을 했었다 cut(x,y)를 만들어서, 반복적으로 정사각형으로 도형을 쪼개서 문제를 해결 한다 Code import sys N = int(input()) paper = [list(map(int, input().split())) for _ in range(N)] white, blue = 0, 0 def cut(x,y,n): global white,blue check = paper[x][y] for i in range(x,x+n): for j in range(y,y+n): if check !..
