전체 글

백준 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과 같은 웹 서버를 내장한다. 스프링을 왜 만들었는가? : 핵심 개념(컨셉) -> 스프링은 자바 언어 기반의 프레임워크 -> 자바 언어의 가장 큰 특징은 "객체 지향"언어 -> 스프링은 객체 지향 언어가 가진 강력한 특징을 살려내는 프레임워크 -> 좋은 객체 지향 애플리케이션을 개발할 수 있게 도와주는 프레임워크 좋은 ..

git 명령어 정리

github 등록 - 파일 수정할 때마다 다음 과정 반복(git checkout -- [file] : 수정사항 원상복귀) -> git add [file] or git add . (모든 파일) git reset [file] -> git commit -m "[message]" -> git push 커밋 내역 수정 - git pull : remote repository -> local repository(git fetch + git merge) - git log : git 기록 - git reset --hard [hash값] : hash값에 대한 commit 이후의 commit들 local repository에서 제거 -> git push -f 로 강제 push해주면 remote repository에도 반영 ..

Python 문법

알고리즘을 위한 기본적인 파이썬 문법(몰랐던 부분만 기록) 자료형 수 자료형 10억 -> 1e9와 같이 거듭제곱 표현 가능 컴퓨터는 실수를 정확히 표현하지 못한다. 그래서 실수 값을 제대로 비교하지 못해서 발생하는 에러들을 방지하기 위해 round()를 사용하는 것을 권장한다. round(실수, 소수점) : 반올림 a = round(765.456, 2) print(a) # 결과 765.46 파이썬은 '/' 연산시 실수형 취급, 몫은 따로 '//' 연산자 사용 '**' : 거듭제곱 연산자 int의 범위 따로 고려x, int(data, radix)로 형변환 가능 ASCII(ord()) 문자(chr()) : 서로 간 형변환 리스트 자료형 빈리스트: list() or [ ], 초기화 : a=[0]*n 슬라이싱 ..