Algorithm

[자료구조] Single Linked List 예제 코드#1 (C)

Single Linked List 구현하기 #1 list의 크기를 입력받고 순서대로 value를 입력받아 동적할당 받은 list노드를 서로 연결해서 linked list로 만들어주었다. 구현을 위한 메서드들 typedef sturct _intlinked : list의 한 노드를 구성하는 구조체 il* make_node() : list의 헤더를 만드는 함수 void add_node(il* head, int value) : head 노드 뒤에 value값을 가진 노드를 연결해주는 함수 void destroyall(il* head) : head 노드부터 시작해서 list의 끝까지 메모리를 해제해주는 함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

[백준 1708] 볼록 껍질 C++

1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net Convex hull jarvis march와 graham scan 알고리즘은 그림도 없고, 설명도 많이 부족하니 다른 분들의 글을 참고해주세요 코드는 determinant를 사용한 풀이입니다 1. 문제 해결 아이디어 Convex hull 문제를 해결하기 위한 대표적인 2가지 알고리즘에는 Jarvis march(gift wrapping) 알고리즘 Graham scan 알고리즘 위 2개가 있다. Jarvis march(gift wrapping)..

[백준 17387] 선분 교차 2 C++

17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을 공부했다. 1. 문제 해결 아이디어 먼저 두 선분이 교차하는 경우를 알아보자 l1선분의 p1, p2벡터에서 l2선분의 p1으로의 방향과 p1, p2벡터에서 l2선분의 p2로의 방향이 서로 다르다면(한 점이 선분에 포함된 경우 포함) 반드시 두 선분은 교차한다. 두 선분의 직선의 방정식을 구해서 교차하는 한 점을 구하면 선분이 교차하는지 알 수 있지 않을까요? 알 수 없다 아래 두 선분을 보자 l2선분을 직선으로 만들면 l1과 교차하게된다. 하지만 l1과 l2..

[백준 2150] Strongly Connected Component C++

2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 강한 연결 요소 ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다. 1. 문제 해결 아이디어 위와 같은 그래프를 Graph라고 하자 Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다. Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기) DFS를 하면서 각 정점의 finis..

[백준 1600] 말이 되고픈 원숭이 C++

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 1. 문제 해결 아이디어 이동할 수 있는 방향이 동서남북 외에도 체스의 말(house)이 움직일 수 있는 8방향이 추가된 문제이다. 처음엔 그냥 8방향만 추가해 주고, 말이 움직이는 방향을 먼저 탐색해 주면 풀리겠지 해서 빠르게 틀렸다. [백준 14442] 벽 부수고 이동하기2 C++ 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 ..

[백준 8980] 택배 C++

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 | 정렬 1. 문제 해결 아이디어 [백준 1700] 멀티탭 스케줄링 C++ 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면 hyeo-noo.tistory.com 위 문제와 비슷한 느낌이다. 미래에 배송될 정보들을 모두 알고 있으므로 마을에 도착해서 박스를 받을 때마다, 먼저 도착하는 마을에 배..

[백준 1167] 트리의 지름 C++

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리, DFS 약 7개월 전에 자료구조 수업에서 트리를 공부하고 풀어보려고 시도했었지만 실패했었던 문제 알고리즘 수업에서 트리의 지름을 구하는 '머리끄댕이' 알고리즘을 배우고 이 문제가 생각나서 적용해서 풀어보았더니 바로 풀림! 1. 문제 해결 아이디어 트리의 지름을 구하기 위한 ㅈㅎㄱ 교수님의 '머리끄댕이' 알고리즘을 알아보자 이러한 트리가 존재하고 지름을 구하기 위해 쭉 늘려보았다 여기서 X는 트리에 있는 임의의 정점이다. X를 잡고 쭉 늘어..

[백준 1328] 고층 빌딩 C++

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데 이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다) 일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다. dp배열을 정해주는 건 어렵지 않았다. 그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다. 그런데 점화식을 도출하기가 정말 어려웠다. ..

[백준 4811] 알약 C++

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다. 한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다. 재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고 마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다. 2. 코드 top d..

[백준 2240] 자두나무 C++

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 cnt초가 지났고, s번 움직였고, 사람 자두가 loc에 있을 때의 최댓값을 메모이제이션 해주었다. 사람의 위치가 그대로 라면 cnt가 T가 되기 전까지 진행이 가능하다. 사람의 위치를 바꾼다면 s가 W가 되기 전까지 위치를 바꿀 수 있다. 현재 위치에 따라서 자두를 먹는지, 못 먹는지를 판단해서 결과에 1을 더할지 말지를 결정한다. 2. 코드 top-down 방식으로 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 ..