코드 낙서장

9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 확인 다익스트라 알고리즘을 활용하는 문제입니다. 풀이 방법은 2가지가 있으며 두 방법 모두 비슷한 결과로 나옵니다. 1번의 다익스트라 알고리즘을 수행하면서 g-h 간선을 지나는 경우를 체크하는 방법 start-g + g-h + h-dest 혹은 start-h + h-g + g-dest 가 start-dest와 값이 같은지 확인하는 방법, 3번의 다익스트라 알고리즘을 수행 결과가 비슷한 이유는 기존 다익스트라 알고리즘 계산 시 dist, graph 배열..

www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 문제 확인 게임트리 문제입니다. 풀이 가지고 갈 수 있는 돌의 개수는 1, 3, 4개 이므로 현재 플레이어가 이길 수 있는 경우의 수는 현재 남은 돌에서 x 개를 가져가서 1, 3, 4를 만들 수 없는 수의 돌을 남기는 것입니다. 따라서 2, 7, 9, 14 .. 가 되며 이는 7로 나눈 나머지가 2, 0 인 경우입니다. 코드 1 2 3 4 5 6 7 8 9 10 #include int main() { long long n; scanf("%lld", &n); if (n % 7 == 0 || n % 7 == 2) printf(..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 확인 배열 인덱스를 따라가면서 만족하는 인덱스를 찾는 방식으로 풀 수 있습니다. 스택을 활용하여 문제를 풀어도 비슷한 결과가 나옵니다. 풀이 2가지 경우로 나눕니다. 전에 입력받은 탑의 크기가 현재 탑 보다 큰 경우 : 현재 탑이 발사한 레이저 신호를 수신한 탑은 i - 1이 됩니다. 현재 탑이 작은 경우 : i - 1부터 수신 가능한 탑을 찾아 내려갑니다. i - 1 번째 탑이 발사한 레이저 신호를 어느 탑이 수신하였는가(dist[i-1])를 보고 수신..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 문제 확인 단순 구현 문제입니다. 풀이 기둥, 보가 설치된 것을 확인하기 위해 ary[101][101][2] 로 선언합니다. 각 ..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 확인 구현, 완전 탐색 문제입니다. 풀이 초기 자물쇠 lock의 홈의 개수를 저장해 둡니다. 매번 확인 시 배열을 회전하지 말고 처음에 key 배열을 회전하여 따로 저장합니다. 이를 통해 메모리 검색 시간과 회전 비용을 줄일 수 있습니다. 완전 탐색 범위는 초기 위치 (i, j) : 1 - key.size() ~ n, 배열 조건 검사 위치 (ki, kj) : 0 ~ m까지 탐색하게 됩니다. 이로 인하여 비교할 값은 lock[i + ki][j + kj]..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 문제 확인 문제에서 주어진 대로 구현하면 되는 문제입니다. 풀이 올바른 문자열 인지 판단하는 방법은 문자열을 검색하면서 ( : +1, ) : -1을 해 주면서 값이 항상 양수라면 올바른 문자열, 한 번이라도 음수 값이 된다면 올바르지 못한 문자열이 됩니다. 괄호 문자 (, ) 은 아스키 값으로 72, 73이며 붙어있는 수 이므로 xor 1을 통해 간단하게 서로 바꿀 수 있습니다. 코드 1 2 3 4 5 6 7..

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 문제 확인 경로를 합칠 수 있으면 길이가 단축되므로 경로들을 정렬해서 합칠 수 있는지 확인하는 스위핑 문제입니다. 풀이 출발지가 목적지보다 왼쪽, 낮은 수인 경우 M으로 가는 도중 처리할 수 있으므로 배열에 넣지 않습니다. 배열에는 목적지가 출발지보다 왼쪽에 있는 경우만 선택해서 담아 이를 목적지 기준으로 정렬합니다. 경로를 합칠 때 돌아갔다가 오는 길이를 줄이기 위해서는 서로 겹치는 부분이 있는 경우만 합쳐서 새 경로를 만들어 줍니다. 예를 들어 다음과 같은..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 확인 map, set을 이용해 해쉬로 풀어도 되지만 느리므로 투 포인터 알고리즘으로 풉니다. 풀이 2개의 수를 잡아서 어떠한 수를 만들 수 있는지 확인하는 방식은 O(N^2), 하나의 수를 잡고 이 수를 만들 수 있는지 확인하는 방식 또한 O(N^2)지만 전자의 경우 그 수가 배열 안에 있는지 확인해야 하는 작업이 필요하므로 더 많은 시간이 필요합니다. 투 포인터 알고리즘을 사용하기 위해 먼저 정렬을 합니다. 그 후 두 포인터를 0, n-1에 두고 현재 확인할 수를 i : 0~n-1로..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 확인 스트링 처리 문제입니다. 풀이 문제 조건에 따라 경우의 수를 나눕니다. 압축한 패턴이 반복되는 횟수가 1인경우 패턴 그대로 입력합니다. 반복 횟수가 2 이상인 경우 : 길이가 1인 경우 "a2", "aa" 같으므로 length + num, 그 이상인 경우 length + num로 해결할 수 있습니다. num은 횟수를 문자열로 나타냈을때 길이이므로 log10을 취해 구할 수 있습니다. 코드 ..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 확인 경로 탐색 문제입니다. 단순 dp로 풀 수 있지만 최대 경우의 수 dp[10][1000][1000] 보다 bfs, 가지치기가 경우의 수가 적으므로 bfs으로 풉니다. 풀이 문제에서 핵심은 벽을 부수는 경우 최단경로가 달라질 수 있다는 점입니다. 따라서 벽을 부순 횟수에 따라 방문했던 칸을 다시 방문할 수 있으므로 다음과 같이 풀 수 있습니다. 처음 방문 : 현재 벽을 부순 횟수 k를 기록합니다. n번째 방문 : 기록된..