본문 바로가기
728x90

코딩187

[자바] 백준 16953번: A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 좀 전에 풀었던 문자열 바꾸기와 굉장히 닮은 문제였다 마찬가지로 큰 수를 작은수로 바꿔나가는 편이 좋을 것 같다는 판단 A를 B로 만들기 위해서 두 가지 방법은 1번) 2를 곱하거나, 2번) 10을 곱하고 1 더하기 (뒷자리에 1을 붙이는것) 이다. 10을 곱하고 1더하는 방법이 수를 더 크게 부풀리기 때문에 이 방법을 많이 써야 연산횟수를 줄일 수 있다. . . A를 B로 바꾸려고 하면 너무 많은 경우의 수가 생기기 때문에, B를 감소시켜 A로 만들어야 한다. B의 끝자리 숫자가 1이고, 10으로 나눴을 때 A보다 크다.. 2022. 12. 30.
[자바] 백준 12904번: A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net S문자열로 T를 만들려면 너무 많은 경우의 수가 생긴다. 그래서 반대로 T문자열을 하나씩 줄여서 S가 될 수 있는지 확인하는 방법을 쓰기로 했다. 문자열 T가 S와 같은 길이가 될 때 까지 끝에서부터 한 문자씩 뗀다. 끝에있는 문자가 A라면 그냥 떼고 끝에있는 문자가 B라면 뗀 후에 문자열을 뒤집는다. 마지막으로 T와 S가 같은 길이가 되었다면 T와 S가 같은.. 2022. 12. 30.
[자바] 백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 인접행렬로 코드를 작성했다가 메모리초과가 났다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P24479 { st.. 2022. 12. 30.
[자바] 백준 1929번: 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 중학교 다닐 때 수학시간에 선생님이 이건 솟수로 발음해야한다고 하시면서...설명해줬던게 갑자기 생각이 났다 1보다 큰 정수 중 1과 자기자신만을 약수로 가진 수를 소수라고 하는데 X 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 .. 2022. 12. 30.
[자바] 백준 1931번: 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 동작 설명 각각의 회의 정보를 입력받는다 입력받은 회의들을 끝나는시간을 기준으로 오름차순 정렬한다. d[]라는 배열을 하나 만들어서 d[i] 에는 i시간까지 수행가능한 최대 회의 개수를 저장할 수 있도록 했다. 이제 각각의 회의들을 순회하면서 d[]배열을 채우면 된다. d[i]는 d[i-1]로 일단 값을 갱신한다 (i시간에는 당연히 i-1시간보다 더 많은 회의를 수행하거나, 같은 수의 회의를 수행할 것이니까) 그리고 i시간에 끝나는 회의를 찾는다. d[해당회의 시작시간]+1한 값과 현재 d[i]값을 비교해서, 더.. 2022. 12. 29.
[자바] 백준 2212번: 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 설명 어느 한 영역에 집중국을 두 개 세우게 되면, 그 영역을 두 개의 영역으로 나눌 수 있게 된다. 그럼 집중국은 어디에 세우는게 좋을까? ->센서와 센서 사이 거리가 가장 긴 곳을 기준으로 영역을 나누면 될 것 같다. ->집중국이 K개면 거리가 가장 긴 K-1개의 영역을 선택하면 된다. 그럼 영역이 K개로 나뉘고 각각의 영역에는 집중국이 하나씩 있다고 생각하면 된다. .. 2022. 12. 25.
[자바] 백준 11000번: 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 프로그램 동작 설명 수업시간이 가장 많이 겹칠 때, 겹치는 수업의 개수가 몇 개인가? 저번에 풀었던 문제처럼~ 뭔가 스택이나 큐같은걸 써야하나 곰곰이 생각해봤는데 우선순위 큐를 사용하는게 좋을 것 같았다. 각각의 수업을 Job이라는 클래스를 이용해서 표현하려 했다. 멤버변수로 수업의 시작시간, 끝나는시간인 start - end가 있다. 우선순위 큐는 Job들을 담을 건데, job의 end(수업의 끝나는시간)을 기준으로, 가장 작은게 head에 .. 2022. 12. 25.
[자바] 백준: 2493 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 처음 작성했던 코드(실패) 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; import java.util.Vector; public class Main { publi.. 2022. 12. 23.
[C언어] 백준 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS,BFS를 예전에 파이썬으로 처음 배웠는데, C언어로 다시 해보려니 기억도 가물가물하고 익숙치가 않다 #include #pragma warning(disable:4996) short int graph[1001][1001] = { 0, }; short int visited[1001] = { 0, }; int queue[1001]; int N; void df.. 2022. 11. 25.
백준 15686번: 치킨 배달(구현, python) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로.. 2022. 8. 31.
구현: 기둥과 보 설치 (python) https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기둥이 조건에 맞는지 확인하고 True,False로 리턴하는 함수 1개 보가 조건에 맞는지 확인하고 True,False로 리턴하는 함수 1개를 우선 만들었다 기둥 설치시 조건확인함수를 돌려 True일 때 설치했다 기둥 삭제시 기둥을 우선 삭제한 다음, 남은 기둥과 보에 대해 조건확인을 싹 다 돌려 하나라도 False를 반환하는 경우 기둥을 다시 추가하여 기둥삭제 명령을 무시하도록 했다 보 설치시 .. 2022. 8. 31.
백준 3190번: 뱀 (구현) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀.. 2022. 8. 30.
이코테 구현: 자물쇠와 열쇠 def solution(key, lock): answer = False new_lock=[[0]*(2*len(key)-2+len(lock))for i in range(2*len(key)-2+len(lock))] for i in range(len(lock)): for j in range(len(lock)): new_lock[len(key)-1+i][len(key)-1+j]=lock[i][j] for i in range(len(key)-1+len(lock)-1): #열쇠 가로로 이동 for j in range(len(key)-1+len(lock)-1): #열쇠 세로로 이동 for k in range(4): #회전 4번 key=turn_90(key) #키 회전 #키 맞춰보기 for a in range(len(.. 2022. 8. 29.
이코테: 구현 - 자물쇠와 열쇠 https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음부터 다 구현하기는 힘들것같아서... 우선은 자물쇠와 키의 크기가 같을 때 회전만 해서 자물쇠를 따는걸 구현해보았다 def solution(key, lock): answer = False return answer def turn_90(key): #행과 열을 바꿔서 90도 회전 length=len(key) result=[] for i in range(length): tmp=[] for j in .. 2022. 8. 29.
문자열 압축 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1글자씩 묶을 때, 2글자씩 묶을 때, . . . 각각을 다 계산해보고 가장 작은 값을 출력하도록 했다 내가 짠 코드는 실행이 안 돼서 결국 다른 코드를 참고했다 def solution(s): result=[] if len(s)==1: return 1 for i in range(1, len(s)//2+1): b='' cnt=1 tmp=s[:i] #시작부터i개만큼의 문자열 for j in range.. 2022. 8. 28.
무지의 먹방라이브 https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 무지의 먹방 라이브 * 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 .. 2022. 8. 24.
알고리즘 기출문제: 그리디2 볼링공 고르기 볼링공 개수n, 볼링공의 최대무게m이 주어지고 다음 줄에 각 볼링공의 무게가 주어진다 두 사람이 서로 다른 무게의 볼링공을 고르고자 할 때, 고를 수 있는 조합의 개수는? n,m=map(int,input().split()) balls=list(map(int,input().split())) result=0 for i in range(n-1): for j in range(i,n): if balls[i]!=balls[j]: result+=1 print(result) 2022. 8. 17.
알고리즘 기출문제: 그리디 1. 모험가 길드 n명의 모험가가 있다 각각의 모험가는 공포도가 있는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 모험을 떠날 수 있다 최대 몇개의 모험가 그룹을 만들 수 있을까? n=int(input()) data=list(map(int,input().split())) data.sort() result=0 count=0 for i in data: count+=1 if count >= i: result+=1 count=0 print(result) 모험가를 한 명씩 데려와서 count를 세고 현재 모험가의 공포도보다 count가 크거나 같다면 result+=1, count는 초기화 한다 2. 곱하기 혹은 더하기 각 자리가 숫자로만 이루어진 문자열 S가 주어진다. 왼쪽부터 .. 2022. 8. 16.
백준 1806번: 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며.. 2022. 8. 15.
기타 알고리즘: 투 포인터 알고리즘, 구간 합 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다 투 포인터 알고리즘을 잘 활용할 수 있는 문제로는 '특정한 합을 가지는 부분 연속 수열 찾기' 가 있다 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2. 현재 부분 합이 M과 같다면, 카운트한다. 3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. n=5 #데이터의 개수 5개 m=5 #찾고자 하는 부분합 m=5 data=[1,2,3,2,5] #전체 수열 count=0 interval_sum=0.. 2022. 8. 15.
728x90

티스토리툴바