https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 단순하게 생각하면 금방 풀 수 있다. 예를 들어 6 2 3 7 5 1 4 로 주어졌을 때, 각 학생이 옮겨지는 횟수는 자신보다 앞에 있는 수 중에서 자신보다 큰 수의 개수이다. 위의 예시로 봤을 때 다음 표와 같이 된다. 키 6 2 3 7 5 1 4 옮겨지는 횟수 0 1 1 0 2 5 3 여기서 옮겨지는 횟수를 모두 더하면 된다. 코드로 옮겨보면 간단하다. int cnt = 0; for (int i =..

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 이 문제는 시간복잡도가 아주 중요한 문제이다. 단순하게 생각하면 금방 풀 수 있지만, 그러면 대다수는 시간복잡도에 걸린다. 내가 처음으로 제출한 코드는 다음과 같다. static void pro() { int deltaX = 1; int deltaY = 1; while (t-- > 0) { if (p == w) deltaX = -1; if (p == 0) deltaX = 1; i..

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에는 loop를 생각했는데 주제가 해시다보니 해시로 풀었다. 실전에서는 이렇게 문제 유형이 나오지 않을텐데 걱정이다 ㅠ HashSet을 사용해도 되나 사용하지 않은 이유는 HashMap에 비해 느리다는 단점이다. 간단히 HashSet과 HashMap 의 차이점을 짚고넘어가자. - HashSet : 순서의 의미를 두지 않으며 데이터의 중복이 없다. 오직 객체만 저장가능하..

https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 배열의 중복값을 제거한 뒤 값을 비교하면 되는 간단한 문제이다. HashSet은 Set 인터페이스에서 지원하는 구현클래스로 중복을 허용하지 않는다. 또한 순서도 없다. import java.util.HashSet; class Solution { public int solution(int[] nums) { HashSet hashSet = new HashSet(); fo..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제의 조건 - 0과 1로만 이루어진 수를 이진수라고 한다. - 다음 조건을 만족하면 이친수라고 한다. 1. 이친수는 0으로 시작하지 않는다 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. - N자리 이친수의 개수를 구하는 문제 d = [0]*91 n = int(input()) d[1] = 1 d[2] = 1 for i in range(..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 인접한 자리의 차이가 1이 나는 수를 계단 수라고 한다. - 예 : 45656 - 길이가 N인 계단 수의 개수를 구하는 문제 D[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수 D[i][j] = D[i-1][j-1] + D[i-1][j+1] ( 1

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건 - 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 - 단 같은 수를 두 번 이상 연속해서 사용하면 안된다. - n=4 - 1+2+1 - 1+3 - 3+1 * 조건 때문에 점화식을 그대로 사용할 수 없다. -> 그 조건을 점화식에 넣기 D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j ... + 1 = i -> D[i][1] = D[i-1][2] + D[i-1][3] .....

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제의 조건 - 카드 N개를 구매해야 한다. - 카드팩은 총 N가지 종류가 존대한다. - i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]원이다. - 카드 N개를 구매하는 비용의 최소값을 구하는 문제 n = int(input()) card = [0] card += list(map(int, input().split())) dp = [0 for _ in range(n+1)] dp[1] = car..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net [문제의 조건] 1. 카드 N개를 구매해야 한다. 2. 카드 팩은 총 N가지 종류가 존재한다. 3. i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]이다. 4. 카드 N개를 구매하는 비용의 최대값을 구하는 문제이다. D[N] =카드 N개를 구매하는 최대 비용 = max(D[N-i] + P[i]) (1

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이 문제는 이전에 풀었던 11276 2*n 타일링 문제에서 조건이 추가된 문제이다. 이전에는 마지막에 두 가지 경우가 올 수 있었으나, 이 문제의 경우에는 세가지 경우가 올 수 있다. 그러므로 이 문제의 점화식은 D[n] = D[n-1] + D[n-2] * 2 이다. n = int(input()) D = [0 for _ in range(n+1)] if n == 1: print(n) elif n==2: print(n+1) els..