https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1. Logic 기본 BFS 문제이다. 최소 이동을 고르기 때문에 우선순위 큐를 활용해서 버튼을 누르는 횟수가 가장 작은것들을 먼저 빼줬고, if문으로 조건을 나눌 때 계속 OutOfBounds가 나와서 잠깐 막혔는데, if문에서 거를 때 조건 두개가 and연산으로 묶여있으면 앞에 조건을 먼저 탐색하기 때문에if문 조건 순서를 바꿔서 해결해줬다 if(cur-d >= 1 && !vis[cur-d]) 이 부분에서..
전체 글
https://www.acmicpc.net/problem/1606 1606번: 침투 계획 세우기 첫째 줄에 멍멍이의 금고의 위치를 나타내는 좌표가 주어진다. 각 수는 0이상 1,000,000이하의 정수이다. www.acmicpc.net 1. Logic x가 0이고 y>0인경우 6*i씩 증가하는 등차수열의 규칙을 가지는 것을 확인할 수 있다. 그리고 모든 입력은 양수로 주어지는 부분에 초점을 맞추면, 1을 제외한 껍질 만큼(x+y) 6을 곱해서 더해주고 만약 y가 0이면 껍질이 하나 생기는 것이기 떄문에 1을 더해준다 2. Code #include using namespace std; int main() { int x, y; cin >> x >> y; long long ans = 1; for(int i =..
https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 1. Logic CCW알고리즘을 활용하여 풀이 가능하다. CCW 알고리즘이란 임의의 선분을 기준으로 다른 한 점이 시계방향으로 위치하는지 반시계방향에 위치하는지 판별할 수 있는 알고리즘이다. 이 알고리즘은 수학시간에 했던 신발끈 공식, 외적을 생각하면 쉽게 이해할 수 있다. 한 선분(선분을 이루는 두 점 A, B)과 다른 한 점(C)을 외적한 값을 CCW(A, B, C)=outer라고 했을 때 outer > 0 : ..
1. Atomic이란? Atomic의 Atom은 원자라는 뜻이며, 원자란 물질을 구성하는 더 이상 쪼개질 수 없는 가장 작은 단위를 말한다. 프로그래밍에서의 Atomic한 실행이란 어떤 연산이 분할되지 않고 한번의 연산으로 실행되는 것을 의미한다. 설명에 앞서 이 글에서는 프로세스, 스레드를 합쳐서 프로세스 라고만 지칭할 것이다. 가장 대표적으로 Atomic한 연산이 필요한 곳은 Critical Section에 대한 연산이다. 멀티 프로세스 환경에서 여러개의 프로세스가 임계영역에 있는 임의의 count라는 데이터에 접근해서 연산을 할 때 프로그래밍 언어에서는 단지 count++;한줄로 끝나지만 코드가 컴파일 되면 기계어로 번역되어 아래와 같이 약 3단계로 구분된다. count = 1이라고 가정// mov..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 1. Logic 여러가지 방법으로 시도해봤다. 시도한 방법은 1. DFS : DFS로 벽인 부분에서 이동할 수 있는 공간의 크기를 세서 저장했다. 100만개 탐색을 100만번 하니 당연히 터질 수 밖에. 그래서 DP로 접근했다. 2. DP : 한 정점에서 다른 정점으로 가는 방법을 DP로 하면 방향이 일정하기 때문에 값이 구해지지만 이번 문제는 상하좌우를 판단해야 하기 때문에..
https://www.acmicpc.net/problem/2236 2236번: 칩 만들기 당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 www.acmicpc.net 1. Logic 선을 하나의 칩에 연결하면 제곱, 두개의 칩에 연결하면 연결한 두 칩의 중요도를 제곱한다. 어떤 경우든 항상 제곱하는게 이득이기 때문에 그냥 정렬해서 큰거만 k개만큼 뽑아주면 된다 풀면서도 이게 맞나 싶었다ㅋㅋㅋㅋㅋㅋ 2. Code #include using namespace std; int n, k; vector input; queue q; int trace[51]; int mai..
https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 1. Logic 단순 파싱 그래프 구현 문제였다. 어렵진 않지만 c++로 파싱하려니 귀찮았다. 2. Code #include using namespace std; int n; int mine[1001][1001]; int sum[1001][1001]; char ans[1001][1001]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[..
트리의 순회 방법에 대해 알아보기에 앞서 트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. 전위 순회 / PreOrder 순회 순서 : [ 루트 노드(부모 노드) > 왼쪽 노드 > 오른쪽 노드] 순서로 방문한다. 위의 그림에서 전위 순회한 결과 : [1 > 2 > 4 > 8 > 5 > 3 > 6 > 7 ] 2. 중위 순회 / InOr..
트리에 대한 기본적인 배경지식은 아래의 포스팅을 참고하면 좋을 것 같다. https://go2gym365.tistory.com/274 [자료구조] Tree & Binary Tree 1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지 go2gym365.tistory.com 1. Node 구조체 노드는 값과 자식 노드로 left, right노드를 가지고 있다. struct Node { int data; Node* left; Node* right; Node() { left = nullptr; right = nullptr; } }; 2. Binary Tree Cl..
1. Tree / 트리 한개 이상의 노드로 이루어진 유한 집합이며, 비선형 자료구조이다. 하나의 루트 노드 아래에 0개 이상의 자식 노드로 구성된다. 그리고 그 자식 또한 0개 이상의 자식 노드를 가지고있고 무한히 반복가능하다. 컴퓨터의 디렉터리 구조가 대표적인 트리 구조로 이루어져 있다! 1-2. Tree 용어 루트 노드(root node) : 부모가 없는 노드. 트리에는 오직 하나의 루트 노드만이 존재한다. 리프 노드, 단말 노드(leaf node, terminal node) : 자식이 없는 최말단 노드 내부 노드, 비단말 노드(internal node, nonterminal node) : 단말 노드를 제외한 나머지 노드 가지, 링크(branch, link, edge) : 노드와 노드를 연결하는 선...