분류 전체보기
-
[백준] 1520번 내리막길문제 풀이 2020. 4. 5. 17:57
1520 내리막길 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이..
-
bit-mask잡다한 지식 2020. 4. 4. 18:59
Bit mask 비트마스크 정수를 이진수 표현으로 사용하는 것을 비트 마스크라고한다.((컴퓨터는 정수형 변수를 이진수로 표현.))비트가 1이면, true 켜져있다.비트가 0이면, false 꺼져있다. N개의 비트가 있을 때 정수의 최소값은 0정수의 최대값은 2^N - 1 연산 종류1. AND 연산 : &2. OR 연산 : |3. XOR연산 : ^4. NOT연산 : ~5. SHIFT연산 : a > b : a / 2^b 예를 들어 6개의 비트가 있다면.0 0 0 0 0 0 ~ 1 1 1 1 1 1 : 0부터 63까지 표현이 가능하다.특정 n번째 비트를 1로 바꾸는 방법은int temp =0; temp |= (1
-
[백준] 1194번 달이 차오른다, 가자카테고리 없음 2020. 4. 4. 18:44
1194 달이 차오른다 가자 문제민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨벽 : 절대 이동할 수 없다. (‘#’열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1) 달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 ..
-
[백준] 1062번 가르침문제 풀이 2020. 4. 4. 16:38
1062 가르침 문제남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다..
-
[백준] 2225번 합분해문제 풀이 2020. 4. 4. 00:12
2225 합분해 문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이) 다이나믹 프로그래밍 문제였다.배열을DP[K][N] = K개 골랐을 때 합이 N인 경우 라고 생각해줬다. 점화식같은 경우는 아래 그림처럼 이렇게 생각해줬다. 즉, N또는 N보다 작은 숫자를 K-1개로 만들었다면 거기에다가 합이 N이 되도록 하는 수 T를 더해주어 K개의 정수로 N을 만들 수 있다는 ..
-
[백준] 1107번 리모컨문제 풀이 2020. 4. 3. 20:11
1107 리모컨 문제수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 ..
-
[백준] 1181번 단어정렬문제 풀이 2020. 4. 2. 17:14
1181 단어정렬 문제알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오1. 길이가 짧은 것부터2. 길이가 같으면 사전 순으로 입력첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 풀이) sort를 하면 되는 문제였다.1. 길이가 짧은 순으로 2. 길이가 같다면 사전순으로 ((string으로 입력을 받아서 vector에 넣는 방식을 기본적으로 사용했다.)) 2개의 풀이법으로 풀어봤는데첫번째는 vect..
-
[백준] 9466번 텀 프로젝트문제 풀이 2020. 4. 2. 00:05
9466 텀 프로젝트 문제이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않..