본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

 (65)
[백준 / BOJ] 12933 오리 문제 출처 : www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net 오리의 울음소리는 quack이다. 'q', 'u', 'a', 'c', 'k'로 이루어진 문자열이 주어졌을때, 존재할수있는 오리의 최소수를 구하는 문제다. 풀이 구현문제다. 가능한 최소한의 오리 수를 구해야하므로, 'q'를 만났을때부터 시작해서 오리의 울음(quack)을 만들때마다 각 문자열 위치를 체크해준다. 한 오리를 최대한 많이 울게하면 된다. 예를들어, 울음소리가 quqacukqauackck로 주어졌다면 0번 인덱..
[백준 / BOJ] 5635 생일 문제 출처 : www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 각 학생이 이름 년도 월 날짜 로 주어질때, 가장 나이가 많은 학생의 이름, 가장 나이가 적은 학생의 이름을 출력하는 문제다. 풀이 pair로 선언하고 오름차순 정렬하면 끝나는 문제다. vector vec; 처럼 선언하고 {{년도, 월},{날짜, 이름}}이 들어갔을때, 이를 오름차순 정렬하면, 1. 빠른년도순으로 2. 년도가 같으면 3. 빠른 월 순으로 4. 월이 같다면 빠른 날짜 순으로 자동 정렬해준다. 각 벡터의 끝과 시작을 출력하면 된다. 소스코드 https://gith..
[백준 / BOJ] 11067 모노톤 길 문제 출처 : www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 산책코스가있다. 산책코스에는 코너마다 카페가있고, 코스관리자인 김씨는 산책로를 따라갈때 (X,Y)에있는 카페를 몇번째로 방문하는지 알고싶다. n개의 카페 위치(X,Y)가 주어졌을때 카페를 몇번 반복하는지 찾는 문제다. 단, X를 줄일필요없이 항상 모든카페를 방문할수있고, 같은 번호를 갖는 카페는 없다. 모든 코너에서는 90도로 회전해서 이동만할수있다.(대각선 이동이 안됨.) 풀이 우선, 제한시간이 ..
[백준 / BOJ] 14464 소가 길을 건너간 이유 4 문제 출처 : www.acmicpc.net/problem/14464 14464번: 소가 길을 건너간 이유 4 첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다. www.acmicpc.net N마리의 소 C마리의 닭이있다. 각 소는 a초부터 b초까지 길을 건널수있는데, 이때 닭이 소를 도와준다면 한번에 길을 건널수있다. 닭은 정확히 T초에만 소를 도와줄수있다. 소는 최대 한마리만 닭의 도움을 받을수있고, 닭역시 최대 한마리의 소만 도와줄수있다. 이때 도움 받을수 있는 소가 몇마리인지 출력하는 문제다. 풀이 닭이 한번 도와줬다면 다시 도와줄수..
[백준 / BOJ] 18679 Banana 문제 출처 : www.acmicpc.net/problem/18679 18679번: Banana The first line of input will contain a single integer N, the number of words in the dictionary (1 ≤ N ≤ 100). The following N lines will each contain a sentence of the format x = y where x is an English word and y is a Minionese word. The next line wil www.acmicpc.net 입력 받은 문자를 미니언 언어로 바꿔서 출력하면된다. 예를들어, I love banana -> mo amo banana 입력에서 각 문자..
[백준 / BOJ] 14746 Closest Pair 문제 출처 : www.acmicpc.net/problem/14746 14746번: Closest Pair Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In th www.acmicpc.net 수평선 c1위에있는 점 P들이 있고 (c1, P1) (c1, P2) (c1, P3)... 수평선 c2위에있는 점 Q들이 있다. (c2..
[백준 / BOJ] 5397 키로거 [이중 연결 리스트] 문제 출처 : www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거� www.acmicpc.net 주어진 문자열에서 비밀번호를 찾아 출력하는 알고리즘이다. '' 를 입력받으면 커서를 한칸 오른쪽으로 움직인다. '-' 를 입력받으면 커서뒤의 글자를 지운다. 예를들어, A
[백준 / BOJ] 3190 뱀 문제 출처 : www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net N*N보드에서 뱀이 이동한다. 이때, 먼저 뱀의 머리를 움직인다. 뱀의 머리가 도착한 위치에 사과가 있다면, 꼬리는 그대로 있고 머리만 움직인다.(뱀의 몸의 길이가 한칸 늘어남) 아니라면, 몸의 길이를 줄여 꼬리가 위치한 칸을 비워준다. 풀이 처음에 문제 조건을 잘 읽지 않고 풀어서 힘들었다. 먼저 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다.

티스토리툴바