본문 바로가기

ALGORITHM_PRACTICE

 (44)
[프로그래머스] 타겟 넘버 사이트 주소 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘 programmers.co.kr 문제를 잘못이해해서 어렵게 풀었던 문제이다. 답을 보고 "엥? 왜 이렇게 풀지?"하다가 문제를 다시 읽어보고나서 깨닫고 다시 푸니 금방 풀 수 있는 문제였다. 숫..
백준 14890번: 경사로 백준 14890번: 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 단순 노가다로 풀었다. 다른 쉬운 방법이 있을 것 같지만 난 무식하게 행에 대한 연산과 열에 대한 연산을 진행했고, 조건 검사해야 하는 부분이 많아 코드가 엄청나게 길어졌다. 난 이렇게 문제를 풀었다. 1. 전과 같은 층일 때 같은 층 개수 카운터를 해준다. 2. 만약 다른 층일 경우 두가지를 본다 2-1. 두 층의 차가 1이 넘으면 이동할 수 없는 길이다. 2-2. 두 층의 차가 1이면 다음 3-1과 3-2를 확인한다. 3-1. 다음 층이 지금 층보다 높은가..
백준 12100번: 2048 (Easy) 백준 12100번: 2048 (Easy) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 백준 문제 오랜만이다! 그동안 다른 것을 하느라 신경못썼는데 하루에 한문제씩이라도 다시 풀어야겠다. 오늘 푼 문제는 게임 시뮬레이션 문제다. Easy라고 적혀있지만 나에게 있어서 전혀 Easy하지 않은 문제였다. 어떤 게임을 기반으로 만들어진 문제인 것 같은데 난 이런류의 게임을 하지 않아서 머리속에 바로..
백준 3190번: 뱀 백준 3190번: 뱀 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 요즘 알고리즘 푸는게 뜸해졌다. 게을러진거 같다. 다시 집중해서 공부해야 감을 잃지 않을 수 있다! 시뮬레이션 문제로 문제 이해를 하는데 조금 난해했다. 어렸을 때 뱀이 움직이면서 알맹이를..
백준 15736번: 청기 백기 백준 15736번: 청기 백기 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된다. 두 번째 선수는 2의 배수의 번호를 가진 깃발, 2번 깃발을 뒤집는다. 3개의 깃발은 백 청 백의 순서로 놓여있게 된다. 마지막 선수는 3의 배수의 번호를 가진 깃발, 3번 깃발을 뒤집는다. 마지막 깃발의 상태는 백 청 청이 되고, 따라서 백기의 수는 www.acmicpc.net 청기와 백기가 양면으로 있는 깃발이 놓여져있고, 선수들이 n번째 차례일때 n의 배수에 해당하는 깃발들을 뒤집는 게임을 하고 있다. 청기를 뒤집을 경우 백기, 백기를 뒤집을..
백준 1019번: 책 페이지 백준 1019번: 책 페이지 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. www.acmicpc.net 근래 풀었던 문제중에 제일 어려웠던 것 같다. 도무지 풀 방법이 생각나지 않아 구글링을 했다, 와 이걸 어떻게 생각해내는 것일까 라는 생각이 들었다. 책의 페이지까지 나오는 모든 숫자의 개수를 구하는 1줄짜리 간단한 문제이지만 페이지의 범위가 10억까지여서 1부터 N까지 하나하나 계산하다 보면 1억 계산당 1초여서 10억이면 10초가 걸리게 되는 문제가 되어버린다. 그러니 여기서 규칙을 찾고 그 규칙을 코드화하면 된다. 규칙이란 것이 생각보다 어려운데 한번에 이해를 못해서 여러 글을 여러번 읽어봐야했다. 1부터 N까..
LCS 최장 공통 부분 수열 알고리즘 LCS(Longest Common Subsequence) 알고리즘은 두 문자열의 최장 공통부분 문자열을 구하는 알고리즘이다. 문자열 ABCD와 문자열 BCDE가 있으면 이 두 문자열 사이에서 공통으로 갖는 부분 수열인 BCD를 찾는 것이다. LCS의 함수 식은 두 문자열을 한 글자씩 비교하면서 같은 글자일 때 이전 글자 비교에서 찾은 부분 문자열 길이에 +1을 하고, 그러지 않을 경우에는 바로 이전 문자열 길이와, 이전 글자가 현재와 같은 글자에서의 최장 부분 문자열 길이 중 최댓값을 선택하는 것이다. 시간 복잡도는 비교하는 각 문자열의 크기 M과 N만큼 비교를 하기 때문에 O(MN)의 시간 복잡도를 갖는다. 그렇다면 예시로 두 문자열의 LCS를 구해보도록 하자 문자열 ACAYKP과 문자열 CAPCAK의..
백준 2096번: 내려가기 백준 2096번: 내려가기 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 메모리가 4MB이므로 변수의 크기를 최소화 해야한다. dp를 선언할 때 max와 min을 저장하는 것을 따로 설정하고 N만큼 반복하면서 max와 min일 때 모든 경우의 값을 저장하면은 해결이된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int score[3]; int ..

티스토리툴바