스터디/알고리즘 문제풀이
[C++] 백준 14499번 - 주사위 굴리기
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 처음에 문제를 봤을 때 이해가 한 번에 가지 않아 조금 당황했지만 문제를 이해하고 나면 크게 어렵지는 않은 전형적인 시뮬레이션 문제입니다. 크기가 N * M인 지도가 주어지고, 지도의 각각 칸에 숫자가 쓰여있습니다. 주사위가 처음 놓이는 위치가 주어지고, 해당 위치는 지도에 0이 쓰여있습니다. 주사위는 각 면이 0으로 초기화되어있습..
[C++] 백준 2504번 - 괄호의 값
https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택의 활용 문제입니다. 처음에 문제에 접근할 때 임시 변수 tmp에 값을 계산하다가 닫는 괄호(')', ']')가 나오면 이를 ans에 더하는 것까지는 생각하였는데, 그 후 tmp를 초기화해버리면 이전 괄호들의 정보가 날아가기 때문에 고민을 많이 했던 문제입니다. 결국 생각보다 구현이 쉽지 않아 삽질을 조금 하다가 검색을 통해 다음 블로그 글을 참고하였습니다. https://mjmjmj98.t..
[C++] Programmers 2020 카카오 인턴십 - 키패드 누르기
https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr Level 1로 크게 어렵지는 않은 난이도의 구현 문제입니다. 위와 같은 그림으로 핸드폰 키패드가 있을 때, 손가락의 최소 이동 거리와 우선순위(왼손잡이 또는 오른손잡이)를 고려하여 입력으로 주어진 numbers의 번호들을 누르기 위해 어떤 손의 손가락..
[C++] 백준 1182번 - 부분수열의 합
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수의 수열을 입력으로 받고, 그 수열의 크기가 양수인(크기가 1개 이상인) 부분 수열 중 합이 S가 되는 경우의 수를 구하는 문제입니다. 처음에 접근했던 방식으로는, 백트래킹으로 원래 수열을 맨 처음부터 살펴보며 부분 수열을 만듭니다. 원소 개수가 1개 이상인 부분 수열이 만들어지면 합을 구하고 그 합이 S와 같아지면 cnt를 1 증가시킵니다. 백트래킹..
[C++] 백준 12851번 - 숨바꼭질 2
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS문제로 주어진 입력의 현재 위치에서 동생의 위치를 찾으면 동생을 찾는 가장 빠른 시간(최단거리)과 가장 빠른 시간으로 동생을 찾는 방법의 수를 출력하는 문제입니다. boj 1697번 숨바꼭질 문제에서 방법의 수를 출력하는 조건이 추가된 문제로 해당 문제와 13549번 숨바꼭질 3, 13913번 숨바꼭질 4 문제를 풀고 난 후 시도했기 때문에 특별히 시간이..
[C++] 백준 1475번 - 방 번호
www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 방 번호를 입력으로 받아 0~9까지 숫자가 하나씩 들어있는 숫자 세트가 방번호를 위해 몇개가 필요한지 구하는 문제입니다. 입력이 공백으로 분리되어 들어오지 않기 때문에 string으로 입력을 받고 해당하는 숫자 순서의 배열 값을 1씩 증가시킵니다. 단순히 입력으로 들어온 숫자의 갯수를 각각 세어 최대 갯수를 출력하면 되긴 하지만 6과 9는 뒤집에서 각 숫자로 대체할 수 있기 때문에 이를 위한 처리를 해주어야 합니다. 들어온 숫자가 6 또는 9일때 전부 9로 카운트 하여 6, 9의 전체 갯수를 구하고 ..
[C++] 백준 3273번 - 두 수의 합
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 1보다 크거나 같고, 1000000보다 작거나 같은 n개의 서로 다른 양의 정수 수열을 받아 자연수 x가 주어졌을 때 두 수의 합이 x가 되는 수열 안의 쌍의 개수를 구하는 문제입니다. 문제를 푼 지가 조금 오래되어서 처음에 구현하였던 코드는 정확히 생각이 잘 나지 않는데, 처음에는 입력을 배열에 저장하고 합을 확인하기 위해 배열을 이중으로 돌며 더한 값이..