피너클의 it공부방

문제 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 흔한 bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다. 이 문제에서 주의해야 하는부분은 bfs에서 방문한 정점을 저장하는 부분이다. 5에서 8로 갈때 5 -> 6 -> 7 -> 8 5 -> 10 -> 9 -> 8 이렇게 2가지 상황이 나올수 있다. 첫번째 상황에서 방문을 체크해버리면 두번째..

문제 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 입력 받은 값들중 합이 0에 가까운 두 수를 찾는 문제다. n이 100000일때 이중 for문을 돌리면 시간초과가 나기에 모든 값을 찾아보는건 힘들다. 입력 받은 값들을 정렬시킨다음 투 포인터를 이용해 하나씩 합을 맞춰보면 간단하게 풀수 있다. int a, b, sum = 2000000000; int start = 0, end = n - 1; int a와..

문제 : https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다. 문제에서는 총 범위가 10000이고 특정 정점까지의 최소 명령어를 필요로 하는걸 보고 유추할수있다. 우선 D, S, L, R을 먼저 구현한다. int D(int n) { int num = n * 2; if (num >= 10000) return num % 10000..

문제 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제다. 다익스트라 알고리즘은 그래프 문제에서 한 정점에서 모든 정점까지 최소비용이 얼마인지를 구하는 알고리즘이다. int dist[1001]; // 비용 모든 정점으로의 비용을 가지는 배열이다. 처음에는 굉장히 큰 수로 초기화 된다. 다익스트라 알고리즘을 돌리며 계속해서 업데이트 해갈것이다. void dijkstra(int..

문제 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 회문을 찾는 함수를 먼저 만든다. 앞뒤 문자가 같으면 true를 반환하고 앞뒤 문자가 다르다면 false를 반환하게 한다. 문자열을 string str로 입력받고 맨 처음은 int s로 맨 마지막을 int e로 잡는다. 처음의 int s의 값은 0이 되고 int e의 값은 (문자열의 길이 - 1)가 된다. str[s]의 문자와 str[e]의 문자가 같으면 s는 1을 추가하고 e는 1을 뺸다. 이번에도 str[s]의 문..

문제 : https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 가장 오른쪽막대기를 기준으로 잡고 기준 막대기보다 큰 막대기를 찾으면 기준 막대기를 바꾸고 보이는 막대기 개수를 올린다. 위 행동을 계속 반복하면 된다. 무조건 하나는 보이기 때문에 처음 값을 1로 잡지 않으면 틀린다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include us..