준비 VS Code 는 기본적으로 IDE(통합개발환경)가 아니라 editor(편집기)이기 때문에 C/C++ 과 같은 컴파일 언어를 사용하기 위해서는 별도의 컴파일 환경을 만들어주어야 한다. 두 부분을 미리 준비해야 하는데, 하나는 VS Code 에서 확장프로그램을 설치해야 하고, 또 하나는 따로 컴파일러를 설치해주어야 한다.컴파일러는 MinGW 를 사용할 것이고, 확장프로그램은  C/C++ Extension Pack 을 설치해주면 된다.오른쪽 위 목차 선택을 통해서 원하는 곳으로 이동하면서 보면 편하다. 컴파일러 MinGW 설치 https://sourceforge.net/projects/mingw/ MinGW - Minimalist GNU for WindowsDownload MinGW - Minimali..

리스트 컴프리헨션 리스트를 생성해서 값을 담을 때 코드를 더 간결하게 만들어주는 문법이다. 리스트 생성, for 문, 리스트에 대입 등 적어도 3 줄 이상으로 길어질 코드를 한 줄에 담을 수 있게 만들어준다.list_arr = [expression for item in iterable_data]기본적인 문법을 일반화시키면 위와 같다.expression 은 item 이 포함된 표현식으로 이 표현식이 리스트에 들어가게 된다. item 은 iterable 자료구조, 즉 리스트, 튜플, 문자열 등에서 가져오게 되는 각 항목이다. 수학의 조건제시법과 유사하다.위 기본적인 문법에 조건을 넣거나, for 문을 더 사용하는 방식으로 변형해서 사용할 수도 있다. 기본형 예를 들어 1 부터 10 까지 수를 리스트에 담는다..

시간 복잡도 (Time Complexity) 복잡도란 알고리즘이 얼마나 많은 자원을 소비하는지 나타낸다. 같은 동작을 할 때 적은 자원을 소비하는 알고리즘이 성능이 좋은 알고리즘이므로 복잡도는 알고리즘의 성능, 효율성을 나타내는 척도이다.복잡도는 시간 복잡도와 공간 복잡도로 나뉘는데, 시간 복잡도는 알고리즘의 연산 횟수를 말하고, 공간 복잡도는 알고리즘을 위한 메모리 공간을 말한다. 시간 복잡도가 커진다는 것은 연산 횟수가 늘어난다는 것이고, 공간 복잡도가 커진다는 것은 필요한 메모리 공간이 많아진다는 것이다.컴퓨팅 메모리가 부족한 상황이 아니라면 주로 신경써야 할 것은 시간 복잡도이다. 시간 복잡도를 나타낼 때는 다양한 표기법이 사용되는데 주로 사용되는 것이 빅오 표기법이다. 빅오 표기법 빅오 표기법은..

https://www.acmicpc.net/problem/12683문제 각 문제의 정답 확률과 답안 제출 기회를 사용하여 답안을 제출했을 때 모든 문제를 맞아 시험에 합격할 수 있는 확률의 최댓값을 구하는 문제이다.영어 문제이지만, 번역기 정도만 사용해도 이해할 수 있다. 풀이 답안 제출 기회에 따라 풀이가 달라질 것이다. 만약 답안 제출 기회가 단 한 번만 있을 경우, 문제를 풀 때 합격 확률이 가장 높은 답안을 선택하여 제출해야 한다. 이 답안의 합격 확률은 각 문제의 정답 확률들을 곱했을 때의 값 중에서 가장 큰 값이 되며, 따라서 이 답안은 각 문제의 정답 확률 중에서 가장 높은 값들이 선택된 답안이 된다.하지만 답안 제출 기회가 여러 번 있을 경우에는 단순하게 접근하기가 어려워진다. 처음 답안을..

https://www.acmicpc.net/problem/3230문제 첫 번째 경기와 두 번째 경기가 끝난 후에 메달권 선수들을 출력하는 문제이다.첫 번째 경기 순서가 선수의 순서가 된다.각 선수들의 순위는 들어왔을 때의 순위이다. 풀이 선수들의 순위가 들어왔을 때 순위로 주어지기 때문에 순위를 계속 업데이트 해주어야 한다. 따라서 순위가 리스트의 인덱스라고 한다면, 해당 인덱스에 삽입해주어야 한다. 때문에 선수를 append 로 추가하기 보다 insert 로 삽입해주어야 한다.두 번째 경기는 슬라이싱을 이용하여 해당 순위에 따라 잘라주면 된다. 사실 아래 코드의 경우 잘라주지 않아도 정상적으로 동작하지만, 두 번째 경기 출전 선수를 명시적으로 나타내고 싶어 슬라이싱을 통해 잘라주었다.마지막 출력은 pr..

https://www.acmicpc.net/problem/18129문제 주어진 문자열을 주어진 기준 수를 이용하여 암호로 바꾸는 문제이다.문자열에서 대소문자 구분없이 특정 알파벳이 기준 수 이상으로 연속되어 있다면 1, 미만이라면 0 으로 치환하고, 이미 치환된 적 있다면 그 구간을 삭제한다. 풀이 주어진 문자열에서 대소문자 구분없이 특정 알파벳이 연속되어 있는지 확인하려면 문자열의 하나의 문자와 그 다음 문자가 같은지 비교하면 된다. 단 문자열의 끝에 도달하면 비교할 문자가 없어지기 때문에 예외처리가 필요하다. 이 문제에서는 문자열이 모두 알파벳이기 때문에 비교하면 무조건 달라지는 숫자를 문자열 끝에 임의로 추가하여 사용하였다.대소문자 구분을 피하기 위해서는 upper 이나 lower 을 활용하면 될 ..

https://www.acmicpc.net/problem/32174문제 주어진 카드 뭉치를 주어진 방법대로 섞고 난 후에 조커의 위치를 찾는 문제이다.조커는 처음에는 덱 가장 위에 있다. 섞는 방법은 세 가지가 있는데 첫 번째 방법은 아래 카드를 위로 올리는 것이고, 두 번째 방법은 위 카드를 아래로 내리는 것이고, 세 번째 방법은 특정 시점에 섞었던 상태로 덱을 바꾸는 것이다. 풀이 중요한 것은 조커의 위치이다. 즉 나머지 카드들이 무엇이고, 어떤 위치에 있는지는 이 문제에서 관심사가 아니다. 따라서 모든 기준을 조커 위치에 맞추고 생각하는 것이 좋다.첫 번째 셔플 방법은 아래 카드를 위로 올리는 것인데, 조커 위치로 생각해본다면 올리는 경우만큼 내려가는 것이다. 인덱스로 생각해보면 더해진다. 다만 이..

https://www.acmicpc.net/problem/32173문제 학생들이 식당에 줄을 설 때 가장 앞, 가장 뒤 중 하나를 선택하여 설 수 있다. 이때 만족도가 변하는데, 경우의 수 중 가장 높은 만족도를 구하는 문제이다. 풀이 학생에게는 맨 앞에 서거나, 맨 뒤에 서는 두 가지 선택지밖에 없다. 즉 두 경우의 수 중 무엇이 만족도 총합을 가장 높게 하는지 확인하면 된다.조건에 따르면 가장 앞에 서게되면 가장 앞에 서는 학생의 만족도 만큼 총 만족도가 올라가지만, 현재 서있는 학생들의 만족도의 합만큼 총 만족도가 감소하게 된다. 그러나 가장 뒤에 서게되면 해당 학생의 만족도는 0 이므로 총 만족도는 변화하지 않는다. 따라서 어떤 학생이 맨 앞에 서느냐가 만족도에 영향을 준다는 것을 알 수 있다.그..

https://www.acmicpc.net/problem/22233문제 중복이 없는 메모장의 키워드에서 새로 작성되는 글에 사용된 키워드들을 제거했을 때 메모장에 남은 키워드의 개수를 구하는 문제이다. 풀이 가장 먼저 입력되는 값이 40만개까지 가능하므로, 빠른 입출력을 지원하는 sys 를 사용해야 한다.메모장에 저장되는 키워드에는 중복이 없기에 새로 작성되는 글의 키워드를 메모장에서 삭제해주면 된다. 이때 새로 작성되는 글에 사용된 키워드가 메모장에 있는지 먼저 확인해야 하는데, 메모장 키워드들을 리스트로 저장한다면 리스트에서 키워드를 탐색할 때 순차적으로 탐색하기 때문에 시간이 오래 걸릴 수밖에 없다. 즉 in 을 활용해서 리스트에서 특정 값을 탐색할 경우 시간 복잡도는 O(N)이다.따라서 리스트가 ..

https://www.acmicpc.net/problem/1158문제 원을 그리고 앉아있는 사람들에 차례로 번호를 매기고, 특정 번째 사람을 제거해 나가면서 제거된 사람들의 번호인 요세푸스 순열을 구하는 문제이다.제거되는 것은 특정 번째를 기준으로 하지만, 각 사람들의 번호는 처음 차례로 매겨진 번호이다. 풀이 주어진 사람들의 리스트에서 주어진 차례의 사람들을 제거해나가면 될 듯 하다. 파이썬에서 원형을 따로 구현하기 보다는 해당 길이보다 차례가 커지면 차례를 조정해주면 될 듯 하다.그런데 생각해야 하는 것은 사람 한 명을 제거할 때 마다 인덱스로 따지면 두 칸을 이동해야 된다는 것이다. 예를 들어 문제 예시와 같이 7명의 사람과 제거해야 하는 차례가 3인 경우를 생각해 본다면 인덱스에 3을 더할 때는 ..