개발일지

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 분석을 하자면 정수 A 에서 2배를 하거나 뒤에 1을 붙이는 두가지 방법만을 사용해서 정수 B로 바꿀수 있는 경우 몇 회의 시행으로 바꿨는지를 출력, 바꿀수 없는 경우 -1을 출력하면 되는 문제이다. 이 문제를 풀때의 아이디어는 A 에서 B로 바꾸는 과정을 탐색을 통해 하나씩 체크하면서 가도 되지만 그보다는 B에서 A로 바꾸는 과정을 탐색하면서 가는것이 더 이득이라는 것을 이용했다. 풀이방식은 다음과 같다. B → A 1. 현재 B가 짝수인경우 2로 나눈다. 2. 현재 B의 1의 자리수가 1인 경우 1을 제거한다. ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 기존의 다른 탐색문제와 마찬가지로 현재 정점에서 한번에 이동할수 있는 정점들이 정해져있는 문제이다. 조금 특이한 부분은 이동할수 없는 '벽'으로 처리된 부분을 단 한번 부수고 이동이 가능하다는 점이다. 이런 부분 때문에 이 문제가 조금 어렵게 느껴질 수 있는데 이 문제를 풀기 위한 아이디어는 그냥 단순히 벽을 부수지 않고 이동하는 경우와 한번 벽을 부순 경우를 둘로 나누어..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 그래프 이론중 이분 그래프에 대해 학습하기 좋은 문제를 찾아서 한번 이분 그래프에 대해 알아보고 해당 문제를 풀이해보겠다. 먼저 이분 그래프의 정의를 살펴보겠다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 이분 그래프의 예..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 먼저 문제 해석을 하자면 n명의 사람을 두 팀으로 나눌 때 두팀의 능력치 차이가 제일 적은 경우에 대해 그 차를 출력하면 되는 문제이다. 각 인원은 서로 팀이 되는 경우마다 능력치가 바뀌기 때문에 각 인원에 대해 갖는 능력치를 행렬로 입력 받는다. 즉 i와 j가 팀인 경우 (i,j) + (j,i) 가 팀의 능력치로 계산된다. 모든 경우의 수를 구하고 각 경우의 수중에서 최소값을 찾는 문제이기 때문에 브루트포스로 접근하..

이번 포스팅에서는 지난 포스팅 스택의 구현에 이어서 마찬가지로 가장 많이 쓰이는 자료구조중 하나인 큐에 대해서 알아보고 구현해보도록 하겠다. 우선 큐의 사전적인 정의를 살펴보도록 하겠다. https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬 ko.wikipedia.org 큐는 FIFO first in first out 즉 선입선출(先入先出)의 구..