분류 전체보기 (174) 썸네일형 리스트형 [ 자료구조 ] 트리 용어 정리 트리(Tree)는 원소들이 부모-자식의 관계로 저장되는 노드(nodes)들의 집합이다. 비순환적으로 연결되어 있는 그래프로 이해해도 무관하다. 트리를 공부하기 전에 트리와 관련된 용어를 정리할 필요가 있어서 이 글에서는 트리 용어만 다룬다. 트리에는 여러 종류의 노드가 존재한다. 노드란 트리의 꼭지점을 의미한다. 노드의 특성에 따라 이름이 부여되는데, 우리가 살펴볼 노드는 아래와 같다. 각각 어떤 특성이 존재하는지 하나씩 알아보자. 부모 노드, 자식 노드, 루트 노드, 리프 노드(외부 노드), 중간 노드(내부 노드), 조상 노드, 자손 노드 노드(Node) 종류 1. 부모-자식 노드 직접 연결된 두 꼭지점은 부모-자식 관계를 가진다. 여기서 위에 위치한 노드를 ‘부모 노드’, 아래에 위치한 노드를 ‘자식.. [ 백준 3197 ] 백조의 호수 (C++) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 효율성을 고려해야 하는 문제다. 푸는데 꽤 오래 걸렸다... 문제를 읽어보면 알겠지만 얼핏 보면 어려운 문제로 보이지 않는다. 그냥 bfs 또는 dfs를 계속 사용하면 테스트 케이스는 통과한다. 그런데 그렇게 풀면 무조건 시간초과에 걸릴 것이다. 이 문제는 단 한번의 bfs로 해결해야 하는 문제다. 전체적인 알고리즘은 '경로탐색 -> 얼음 녹이기'를 반복하면 된다. 그.. [ 백준 2933 ] 미네랄 (C++) https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 내 수준에서는 좀 어려운 문제였다. 단순 구현 문제긴 하지만 머리를 좀 써야 한다. 우선 큰 그림부터 그려보자. 문제를 풀기 위한 큰그림과 사용하는 변수는 아래와 같다. 1. 막대기로 미네랄 캔다 2. 붕 뜬 클러스터가 있으면 내려준다 char map[101][101] -> 입력값 저장 int visit[101][101] -> 방문 배열 (dfs에서 사용) int sticks[100] -> 막대기 배열 int .. [ 백준 11559 ] Puyo Puyo (C++) https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net dfs를 이용한 재밌는 구현 문제였다. 규칙을 만들고 그대로 구현하기만 하면 되는 문제라 크게 설명할 것은 없다. 인접한 동일 색깔의 개수를 count라고 했을때, dfs 결과 count가 4 이상인 것은 map에서 삭제해주고 붕 떠 있는 것을 아래로 내려주면 된다. 말로 하면 좀 헷갈리니 사진으로 확인하자. 아래는 문제의 테스트 케이스를 돌렸을때 첫 번째 연쇄 과정이다... [ 백준 8911 ] 거북이 (C++) https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 단순 구현 문제다. Turtle 이라는 클래스를 만들어서 풀었다. 정답으로 출력해야 하는 직사각형의 넓이는 거북이의 이동경로에서 가로/세로 최대/최소값의 차이를 곱하면 된다. 문제에서 주어진 네 개의 함수는 그대로 구현했고, 여기에 init() 라는 함수를 추가했다. 이 함수는 거북이가 이동할때마다 x, y의 최대 최소값을 초기화해주는 함수다. 문제가 어렵지 않으므로 바로 정답 코드... #include #.. 엘리스 sw 엔지니어 트랙 2기 지원 후기 엘리스 sw 엔지니어 트랙 2기에 지원해서 최종 합격했다! 엘리스 sw 엔지니어 트랙은 국비지원의 일종으로 내일배움카드 발급 대상자에 한해 지원할 수 있다. 4개월 동안 백, 프런트를 모두 배우고 중간에 두 번의 팀 프로젝트가 있다. 자세한 커리큘럼과 선발과정은 홈페이지에 직접 들어가서 보도록 하자. 나는 협업 경험을 쌓고 싶어서 지원했다. 홈페이지 바로가기 경력에 필요한 경험을 쌓는 길. 엘리스 SW 엔지니어 트랙 엘리스 SW 엔지니어 트랙은 “경력에 필요한 경험”을 원하는 개발자 취업 준비생 분들을 위한 교육 과정입니다. 현업에서 사용하는 기술 스택에 집중하여 배우고, 현업 개발팀 방식 그대로 실 elicetrack.oopy.io 선발 절차는 '서류 - Pre Track - 알고리즘 테스트 - 면접 .. [ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++) 1. 이분탐색 원리 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다. 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있다. 아래 그림을 보자. 배열은 오름차순으로 정렬되어 있다고 가정한다. 배열의 시작점과 끝점의 정중앙에 위치한 값을 '중앙값'이라고 부르겠다. 만약에 그림과 같이 '탐색값 < 중앙값' 이면 중앙값의 오른쪽 부분은 고려할 필요가 없다. 오름차순으로 정렬되어 있기 때문이다. 따라서 이제 끝점은 중앙값이서 1을 뺀 위치가 된다. 끝점의 위치가 이동했으므로 중앙값의 위치도 아래 그림과 같이 이동한다. 이번에는 '중앙값 < 탐색값' 이므로 중앙값의 왼쪽 부분은 볼 필요가 없다. 따라서 시작점은 중앙값에 1을 더해준.. [ 자료구조 ] 큐(Queue) 큐(Queue) 큐는 선입선출(FIFO: First-In First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조다. 데이터 삽입을 enqueue라 하고, 데이터 삭제를 dequeue라고 한다. 그런데 흔히 삽입 및 삭제를 push, pop으로 부른다. 스택과 비교해서 보기를 바란다. 스택은 가장 먼저 들어온 데이터가 가장 마지막에 나가지만, 큐는 가장 먼저 들어온 데이터가 가장 먼저 나간다. 이러한 자료구조가 왜 필요할까? 어떻게 활용할 수 있을까? 가장 대표적인 예시는 '스케줄링'이라고 생각한다. 스케줄링은 쉽게 말해서 '줄 서기' 규칙이다. 마트에서 줄을 서는 경우를 예로 들어 보자. 줄에 가장 먼저 선 사람이 계산을 가장 먼저 하는 것은 당연하다. 티켓팅도 마찬가지다. 가장 먼저 들어온 .. 이전 1 ··· 5 6 7 8 9 10 11 ··· 22 다음
