https://www.acmicpc.net/problem/1503 1503번: 세 수 고르기 첫째 줄에 N(1 ≤ N ≤ 1,000)과 집합 S의 크기 M(0 ≤ M ≤ 50)이 주어진다. 둘째 줄에는 집합 S에 들어있는 수가 주어진다. 집합에 들어있는 수는 1,000보다 작거나 같은 자연수이고, 공백으로 구분되어 www.acmicpc.net 1. Logic 일단 입력받은 집합에 있는 숫자를 제외해야하기 때문에 bool배열을 활용하여 제외해야 하는 숫자들을 걸러줬다. 그리고 N의 범위가 1000까지이기 때문에 브루트포싱을 돌려서 1~1001까지 3중 for문을 활용하여 풀이해줬다. 시간복잡도가 1000^3 만큼 나와서 안될 줄 알았는데 내부 테케가 부족했는지 통과됐다. 이게 왜돼? 2초에 2억번 연산이라..
전체 글
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..