PS
BOJ 15684 - 사다리 조작
www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 처음에 dfs 로 처리하려고 했으나, 사다리가 끝에 도달 했을때, 끝나지 않고 다른 지점을 방문하는 오류를 계속 범하고 있어서 통과하지 못했다. dfs 는 한쪽을 쭉 다 방문한 다음 다른 쪽을 방문하여 전체를 다 방문하는 것인데 문제풀때, dfs 에 대한 개념 자체를 모호하게 이해하고 있었던것 같다. 답을 못 찾다가 다른 분들의 풀이를 보고서 이해하게 되었다. 1. 전체 놓을 수 있는 가로선의 사다리 중 최대..
프로그래머스 - JadenCase 문자열 만들기
programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 단순한 구현 문제다. 소문자, 대문자 구분을 위한 cctype 헤더 파일을 이용해서 아래의 함수들을 사용하면 isupper(), islower(), toupper(), tolower() 더 짧은 코드를 쓸 수 있을 것 같다. 그러나 그냥 아스키코드 값으로 처리하도록 코드를 썼다. - c++ #include #inclu..
프로그래머스 - N 개의 최소공배수
programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 최소공배수(LCM) 은 "두 수의 곱 / 두 수의 최대공약수" 로 구한다. 최대공약수(GCD) 는 보통 유클리드 호제법으로 구한다. - c++ #include #include using namespace std; int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); } int..
프로그래머스 - 이진 변환 반복하기
programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 단순한 구현 문제다. - c++ #include #include using namespace std; vector solution(string s) { vector answer(2, 0); int cnt = 0, zero = 0; while(s != "1") { cnt++; string temp; for (int i = 0; i
프로그래머스 - 행렬의 곱셈
programmers.co.kr/learn/courses/30/lessons/12949# 코딩테스트 연습 - 행렬의 곱셈 [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] programmers.co.kr 가장 단순한 방식으로 행렬의 곱셈을 구현하는 문제이다. 삼중 for문을 사용하면 구할 수 있다. 첫번째 for 문은 arr1 의 행 길이 만큼 두번째 for 문은 arr2 의 열 길이 만큼 세번째 for 문은 arr1 의 열 길이 만큼 돌면서 arr1[i][k] * arr2[k][j] 를 구하면 된다. - c++ #include #include using n..
프로그래머스 - 짝지어 제거하기
programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 프로그래머스 - 올바른 괄호 문제와 똑같은 문제이다. 그냥 스택을 써서, 짝이 맞으면 pop 아니면, push 하면 끝나는 문제다. - c++ #include #include using namespace std; int solution(string s) { int answer = 0; stack st; for (int i = 0; i
프로그래머스 - 땅따먹기
programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr DP 를 이용해 푸는 문제이다. 1행 부터 시작해서 자기자신 보다 바로 윗행 중에서 동일한 열이 아닌 열을 선택하여 값을 더하면서 최대 값을 찾아 갱신하는 방식이다. 점화식으로 쓴다면 대략 이런 모습이 될것 같다 i >= 1, j = 0 일때 dp[i][j] = max(dp[i][j] + dp[i - 1][j + 1], dp[i][j] + dp[i - 1]..
프로그래머스 - 올바른 괄호
programmers.co.kr/learn/courses/30/lessons/12909# 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr 스택의 대표적인 기본 문제이다. 여는 괄호 '(' 가 들어오면 스택에 push 하고 닫는 괄호 ')' 가 들어오면 스택에서 pop 하되, 스택이 비어있지 않아야하며, 동시에 스택의 top 이 여는 괄호 '(' 여야만 짝을 맞춰서 pop 할 수 있다. 그렇지 않은 경우라면 닫는 괄호 ')' 를 스택에 push 한다 (짝을 맞춰서 pop 해야..