본문 바로가기

전체 글

 (140)
[TIL] 99클럽 코테 스터디 7일차 TIL + 프로그래머스 모음사전 문제 풀이 문제 탐색하기DFS 알고리즘을 활용하여 풀이 설계하기깊이 우선 탐색 알고리즘에 대해서는 아래의 게시글에 개념을 설명해두었습니다.https://coding-babo.tistory.com/151 [TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1문제 풀이 문제 탐색하기깊이 우선 탐색(DFS, Depth-First Search)그래프 탐색 알고리즘으로, 노드를 탐색할 때 깊이를 우선하여 끝까지 탐색하는 방식입니다. 시작 노드에서 출발하여 갈 수 있는 만coding-babo.tistory.com DFS는 스택 자료 구조를 사용하여 구현할 수도 있고 재귀호출을 통해 구현할 수도 있습니다.프로그래머스의 모음사전 문제는 재귀호출을 통해 DFS를 구현하였고 완전탐색을 통해 ..
[TIL] 99클럽 코테 스터디 6일차 TIL + 백준 2805 나무 자르기 문제 풀이  문제 탐색하기이분탐색을 활용하여 문제 설계하기이분탐색에 대한 개념은 아래 게시글에 정리해두었습니다!https://coding-babo.tistory.com/148 [TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색문제 풀이 (백준 1072 게임) 문제 탐색하기위 문제를 풀기 위해서는 고려해야할 점이 3가지가 존재합니다.첫번째 부동소수점 오차를 고려해야합니다.두번째 X가 최대 1000,000,000까지 주어질 수 있coding-babo.tistory.com 바로 이분탐색을 이용하여 문제를 파악해보겠습니다.상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어집니다. 적어도 M을 맞추기 위한 절단기의 높이를 구하는 것이 이 문제의 답입니다.여기서 이분탐색을 실행할 범위를 구할 수 있습니..
[TIL] 99클럽 코테 스터디 5일차 TIL + 백준 24444 너비 우선 탐색 1 문제 풀이 문제 탐색하기너비 우선 탐색(BFS, Breadth-First Search) ?그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다. BFS의 동작 원리시작 노드를 큐에 삽입하고 방문 처리를 합니다.큐에서 노드를 하나씩 꺼내 해당 노드의 이웃 노드를 모두 큐에 추가합니다. 추가할 때 이웃 노드가 방문되지 않은 경우만 추가합니다.위 과정을 큐가 빌 때까지 반복합니다.BFS의 주요 특징시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수)로 그래프의 모든 노드를 탐색합니다.장점: 최단..
[TIL] 99클럽 코테 스터디 4일차 TIL + 백준 24479 깊이 우선 탐색 1 문제 풀이 문제 탐색하기깊이 우선 탐색(DFS, Depth-First Search)그래프 탐색 알고리즘으로, 노드를 탐색할 때 깊이를 우선하여 끝까지 탐색하는 방식입니다. 시작 노드에서 출발하여 갈 수 있는 만큼 깊이 들어가고, 더 이상 갈 곳이 없으면 직전 노드로 돌아가 다른 경로를 탐색하는 방식으로 진행됩니다. DFS 는 스택 자료 구조를 사용하여 구현할 수도 있고 재귀호출을 통해 구현할 수도 있습니다. DFS의 동작 원리시작 노드에서 출발하여, 방문한 노드를 스택에 저장합니다.현재 노드에서 갈 수 있는 노드가 있다면, 그 노드를 방문하고 스택에 추가합니다.갈 수 있는 노드가 없으면 스택에서 가장 최근 노드를 꺼내와(백트래킹) 다음 가능한 노드를 탐색합니다.위 과정을 모든 노드를 방문할 때까지 반복합..
[TIL] 99클럽 코테 스터디 3일차 TIL + 프로그래머스 입국심사 (java) 문제 풀이 (프로그래머스 입국심사) 문제 탐색하기이분 탐색 활용하기모든 사람이 심사를 받는데 걸리는 시간의 최소값을 구하는 문제입니다. n이 주어졌고 각 심사관은 1명을 심사하는데 최대 1,000,000,000분의 시간이 걸린다고 합니다.따라서 1분부터 가장 긴 심사 시간*n 까지의 범위에서 모든 사람이 심사를 받을 수 있는 최소 시간을 구해내면 되는 이분탐색 문제입니다. 최소시간을 left로 지정하고 최대시간을 right로 지정해줍니다.그 사이를 mid로 지정해준 다음 주어진 시간동안(mid) 탐색할 수 있는 사람의 총 수가 n보다 작을 경우 left 를 mid+1로 지정해주고 크거나 같을 경우 right를 mid-1로 지정해준다음 탐색을 지속합니다.left가 right보다 커지면 탐색을 종료하고 그 ..
[TIL] 99클럽 코테 스터디 2일차 TIL + 등차수열의 합 문제 풀이 (백준 11561 징검다리)문제 탐색하기문제 풀이 방식 접근징검다리를 건너는 규칙을 살펴보면 두번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다고 되어있습니다.이를 통해 등차수열의 합 공식을 활용해서 문제를 풀어야한다는 것을 알 수 있습니다.등차 수열의 합이 총 징검다리의 개수보다 작거나 같을 경우의 값 = 밟을 수 있는 징검다리의 최대 개수라는 점을 고려하여 문제를 풀면 됩니다. * 등차수열 합 공식?등차수열 합 공식 : n(n+1)/2등차수열의 합 공식을 통해서 징검다리가 10개인 경우와 11개인 경우를 예시로 들어보겠습니다. [ 징검다리의 개수 : 10 ] 징검다리의 개수가 10개인 경우는 1, 3, 6, 10 번째 징검다리를 밟아서 총 4번이 밟을 수 있는 ..
[TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색 문제 풀이 (백준 1072 게임) 문제 탐색하기위 문제를 풀기 위해서는 고려해야할 점이 3가지가 존재합니다.첫번째 부동소수점 오차를 고려해야합니다.두번째 X가 최대 1000,000,000까지 주어질 수 있으므로 시간 복잡도를 고려하여 이분탐색 알고리즘을 활용해야합니다.세번째 승률이 절대 변하지 않는 경우를 생각합니다. * 부동소수점 오차부동소수점 오차는 컴퓨터가 실수를 정확히 표현하지 못해 발생하는 작은 오차입니다. 컴퓨터는 실수를 이진수로 표현하는데, 10진수의 일부 소수점 숫자는 2진수로 완전히 변환되지 않는 경우가 많기에 근사값으로 저장하는 경우가 있습니다. 따라서 이 경우 예상한 결과가 나오지 않을 수 있기때문에 최대한 정수범위 내에서 연산을 하거나 BigDecimal을 사용해야합니다.// 승률을..
[코딩테스트 챌린지] 백준 5567 결혼식 (java) 문제 문제 탐색하기1. 문제 유형 파악하기친구 관계가 주어지는 것을 보았을 때 a와 b는 친구라는 뜻은 b와 a도 친구라는 뜻입니다. 이를 통해서 인접행렬을 통해서 친구관계를 나타낼 수 있었습니다. 또 문제 조건 중에서 결혼식에 초대하는 사람은 상근이의 친구와 친구의 친구까지만 초대하는 조건이 있었습니다. 이를 통해서 dfs 를 구현하되 depth를 2로 제한을 두어 결혼식에 초대하는 동기의 수를 구할 수 있을 것 입니다. 2. 인접 행렬 구현하기입력받는 친구관계를 통해 친구관계 배열인 connect에 친구일 경우 1을 삽입해줍니다.connect[a][b] = connect[b][a] = 1 3. DFS 구현하기dfs를 재귀적으로 호출할때 거치는 친구를 True로 저장하는 배열을 선언합니다.dfs는 상근..

티스토리툴바