전체 글

프로그래머스 - 무지의 먹방 라이브

programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음..

볼링공 고르기

문제 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하라. 입력 첫 째줄 -> 볼링공의 개수 N(1 ~ 1000), 공의 최대 무게 M(1 ~ 10) 둘 째줄 -> 각 볼링공의 무게 K (1 ~ M) 출력 두 사람이 볼링공을 고르는 경우의 수 풀이 1. 각 무게 별로 볼링공의 수가 몇 개인지 count하는 배열을 만든다. ex) 볼링공 5개의 무게가 각각 [1 3 2 3 2]로 주어졌을..

만들 수 없는 금액

문제 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구한다. 입력 첫째 줄 -> N : 동전의 개수 (1 ~ 1,000) 둘째 줄 -> 동전의 화페 단위, N 개의 자연수 (1,000,000 이하) 출력 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값 풀이 1. 먼저 data를 정렬한다. 2. 처음에 금액 1을 만들 수 있는지 확인하기 위해 target=1로 설정한다. 3. 현재 data이 target을 만들 수 있으면 (data값target: break target+=x print(target)

백준 1439 - 뒤집기

www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111..

구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 보통 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열은 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 (순열과 조합을 찾는 경우 등) -> 많은 연습이 필요한 분야이다.(프로그래밍 언어의 문법을 정확히 알고 있어야 한다.) 대표적으로 완전 탐색과 시뮬레이션 유형을 '구현' 유형으로 많이 사용한다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 -> 보통 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적..

그리디

그리디 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디 알고리즘은 다른 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 최단 경로 알고리즘의 경우 플로이드 워셜, 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 그러나 그리디 알고리즘의 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다. +) 그리디는 보통 작은 값 혹은 큰 값부터 처리하는 경우가 많기 때문에 정렬 알고리즘과도 연관이 있다. 예제) 거스름돈 Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈..

복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 일반적으로 코딩테스트 환경에서 O(n3)을 넘어가면 문제 풀이에서 사용하기 어렵다 (c 기준 n의 크기가 5000이 넘어가면 10초 이상의 시간 소요) 다음은 모두 시간 제한이 1초인 문제에 대한 예시이다. N의 범위가 500인 경우 : O(n3)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 5,000인 경우 : O(n2)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 1,000,000인 경우 : O(nlogn)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 10,000,000인 경우 : O(..

[Spring] 객체 지향 설계와 스프링

스프링 핵심 원리 - 기본편 강의를 들으며 생각 정리 초기에 자바 표준 기술 EJB : 기능은 좋은데, 어렵고 느리고 비싸다. -> JPA & 스프링 탄생 스프링이란? 현재 스프링 프레임워크, 스프링 부트, 스프링 데이터 등 다양한 서비스가 있다. - 스프링 프레임워크 : 스프링 DI 컨테이너, AOP (핵심 기술) - 스프링 부트 : 스프링을 편리하게 사용할 수 있도록 지원, Tomcat과 같은 웹 서버를 내장한다. 스프링을 왜 만들었는가? : 핵심 개념(컨셉) -> 스프링은 자바 언어 기반의 프레임워크 -> 자바 언어의 가장 큰 특징은 "객체 지향"언어 -> 스프링은 객체 지향 언어가 가진 강력한 특징을 살려내는 프레임워크 -> 좋은 객체 지향 애플리케이션을 개발할 수 있게 도와주는 프레임워크 좋은 ..