전체 글65 음료수 얼려 먹기 N*M 크기의 얼음 틀.구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1. 생성되는 아이스크림의 총 개수. (뚫려있는 부분은 연결되어있음) 0011000011 1111100000 입력 조건 :첫번째 줄 : 세로 N, 가로 M두번째 줄 ~ 마지막 줄 : 얼음 틀의 형태 출력 조건 :아이스크림 개수 출력 문제 분석 물을 부으면, 이어진 공간에 하나의 아이스크림이 생긴다.이 문제는 DFS로 해결할 수 있다. 예를 들어 아래와 같은 얼음 틀을 살펴보자.001010101 3 묶음을 계산하는 과정을 다음과 같다.1. 시작 지점을 기준으로 연결되어 있는 점 중에서 방문하지 않은 점을 방문한다.2. 또, 상 하 좌 우를 살펴보면서 방문을 다시 진행한다. 3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 .. 2024. 9. 19. [알고리즘] 탐색 알고리즘, BFS BFS(Breadth First Search) 알고리즘은 '너비 우선 탐색' 이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작했다면, BFS는 그 반대이다. 그렇다면 BFS는 실제로 어떤 방식으로 구현할 수 있을까?BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한동작 방식은 다음과 같다. 1. 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐.. 2024. 9. 19. [알고리즘] 탐색 알고리즘, DFS 우선 탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.또한 두 노드가 간선으로 연결되어 있다면, 두 노드는 '인접하다'라고 표현한다. 노드를 도시, 간선을 도로라고 생각해보자. A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서, A와 B를 연결하는 도로(간선)을 거친다고 이해하면 쉬울 것이다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데, 코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있도록 하자. 1. 인접 행렬(.. 2024. 9. 17. [구름톤 유니브 3기] OT 회고 9월 5일 동국대학교 내에서 구름톤 유니브 3기 ot 행사가 있었다.이번 동아리 OT에서는 각 부원들의 자기소개와 스터디별 활동 계획, 그리고 앞으로의 동아리 일정에 대해 소개받았다.새로운 부원들과 인사를 나누며 다양한 전공과 흥미를 가진 사람들과 함께하게 되어 기대감이 컸다. 특히, 스터디별로 구체적인 활동 계획이 소개되었는데, 내가 속한 스터디는 코딩테스트 문제 풀이를 중점적으로 다룰 예정이라 매우 기대가 된다.동아리 일정도 체계적으로 계획되어 있어 앞으로의 활동이 매우 기대된다. 특히, 연말에 있을 연합 해커톤은 나에게 큰 도전이 될 것 같다. 이번 OT를 통해 동아리 활동이 단순한 친목을 넘어 실제로 실력을 쌓을 수 있는 기회라는 것을 확신하게 되었다. 내 역할로는 스터디 내에서 적극적으로 지식을.. 2024. 9. 15. [공통문제] 공 포장하기 빨간 공 R개초록 공 G개파란 공 B개를 가지고 있다.이 공들을 박스로 포장하려고 한다.박스에는 1개, 2개, 또는 3개의 공이 들어갈 수 있다.박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다. 필요한 박스 개수의 최솟값을 구한다. 초기 접근 예를 들어 빨 4, 초 2, 파 4가 있다고 가정하자.우선 박스의 개수가 최소가 되어야 하니, 3개짜리 박스가 많을 수록 좋다.3개를 담아보면 빨 3, 파 3을 담아 2박스가 생기고빨 1 초 2 파 1 이 남는다.또, 여기서 빨초파를 하나씩 담아서 3개짜리 박스를 하나 더 만들 수 있다. 이때 3개짜리 박스를 무조건 많이 만드는게 유리한가에 대해 생각해볼 필요가 있다. 그런데 박스의 개수가 적어야하니, 3개짜리가 많을 수록 유리한것이 맞다. 222라면.. 2024. 9. 13. [2주차공통] 문자열 뒤집기 0과 1로만 이루어진 문자열 S가 있다.이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 0을 1로, 1을 0으로 바꾸는 것이다. 예를 들어 S=0001100일 때 1트 : 전체를 뒤집으면 1110011이 된다.2트 : 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 된다. 하지만 처음부터,처음부터 4번째부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 된다. 초기 접근 우선, 0을 1로 바꿀지, 1을 0으로 바꿀지 둘 중 하나를 선택할 수 있어야 한다. 연속된 수를 뒤집는 것이 1회 실행이므로, 1의 연속된 세트는 몇개인지, 0의 연속된 세트는 몇개인지 계산한 후연속된 세트의 개수가 더 적은 쪽의 세트 개수를.. 2024. 9. 10. 이전 1 2 3 4 5 6 7 8 ··· 11 다음
