코딩테스트 - Week1

백준

문제 : https://www.acmicpc.net/problem/10808 1. 문제 접근 입력으로 들어오는 알파벳의 문자를 count하면 된다 count문제 map을 활용 : 문자열을 count할 때 배열을 활용 : integer을 기반으로 count할 때

1. 문제 접근 자동차 3대가 얼마나 같이 주차되어있느냐를 카운팅 배열로 접근해서, [도착 시간, 출발 시간) 범위를 카운트해줘야 함 2. 시행착오 시간 문제를 다룰 때는(도착/출발, 시작/끝나는시간) 무조건 이상, 미만 구간을 적용해야 한다. ex. 도착시간:1

문제 : https://www.acmicpc.net/problem/10988 1. 문제 접근 팰린드롬을 만드는 방법 문자열의 처음과 문자열의 끝 문자열부터 점차 좁혀가면서 탐색하는 방법을 사용 2. 시행착오 없음 그러나 더 간단한 reverse()방법을 미처 생각하

문제 : https://www.acmicpc.net/problem/9996 1. 문제 접근 문자열 패턴 (ex. c\a)는 \ 앞뒤로 한 글자가 아님에 유의하자. aa\*bb 이런 꼴이 될 수도 있다는 것! 또한 문자열 패턴보다 길이가 작은 글자가 들어오는 경우

문제 : https://www.acmicpc.net/problem/1159 1. 문제 접근 들어오는 문자열의 맨 첫 글자의 개수를 세야하는 코드 문자를 count하기 때문에 배열로 접근하자 2. 시행착오 없음 3. 코드 및 풀이 3.1 배열 풀이 코드에서는 count 변수를 활용해서 기권 여부를 판단했지만, 다르게 할 수 있음 다음과 같이 ret이라...

문제 : https://www.acmicpc.net/problem/2559 1. 문제 접근 1. 누적합을 통한 prefix sum 배열로 해결해야 함 2. 시행착오 코드 자체는 맞긴 했지만, 누적합 배열을 활용해서 더 깔끔하게 짤 수 있던 점을 간과 누적합 배열을 사용하지 않고, 원본 값들을 배열에 그대로 저장하고 presum이라는 변수에 저장하고 ...

1. 문제 접근 해당 문제는 string형을 key, int형을 value로 갖는 map과 int를 key, string을 value로 갖는 map을 통해 풀어야 함 => O(NlogN)으로 풀 수 있음 아니면 숫자를 통해 문자열을 찾는 경우는 배열을 활용해 풀 수 있음 2. 시행착오 입력이 엄청 많이 들어오는 경우(약 20만) 시간초과 문제를 겪음 3...

1. 문제 접근 해당 문제는 경우의 수를 수학적 공식을 활용해서 풀어야 하는 문제 자료구조 map을 활용하여 들어오는 의상의 종류(string)를 Key로 하고, 의상의 이름은 따로 저장하지 않고 갯수만 count해야 함(문자열 count니 map쓰기) 2. 시행착오 1. 의상의 종류, 의상의 이름을 string과 int로 받는 것까진 생각하였으나, 각 ...

1. 문제 접근 선택할 수 있는 경우 중 2개를 선택하는, 조합(combination)을 이용해서 문제를 풀어야 함 2. 시행착오 없음!! 3. 코드 및 풀이 3.1 풀이 2개를 고르는 조합은 for문을 통해 간단히 구현할 수 있음 간혹 시간제한이 엄격한 문제가 존재하기 때문에, m이 200,000이 넘는 경우는 무조건 오답이기 때문에, 바로 오답처리...

1. 문제 접근 스택을 활용하여 문제를 풀어야 함. 스택에 문자열의 문자를 하나씩 넣으면서, 가장 위에 있는 문자열이 새로 push하는 문자열과 비교 2. 시행착오 좋은 단어의 정의를 잘못 이해함 스택을 활용할 때, 스택이 비어있는 경우를 고려하지 못함 3. 코드 및 풀이 3.1 풀이 입력된 각 문자열을 stack을 활용해 좋은 문자인지 좋지 않은...

문제 : https://www.acmicpc.net/problem/1629A, B, C 모두 2^31-1까지 가지는 자연수이고, 거듭제곱을 활용하기 때문에 mod연산 + 분할정복까지 고려해야 한다.제한시간이 0.5초이기 때문에, 분할정복을 활용해서 계산해야 한

문제 : https://www.acmicpc.net/problem/4375마찬가지로 mod연산을 하면서 접근할 수 있다.없음mod 곱셈연산 : (A \* B) mod C = (A mod C \* B mod C) mod b가 홀수인 경우도 나타날 수 있다. (e

문제 : https://www.acmicpc.net/problem/11655 1. 문제 접근 'Z'나 'z'에 13을 더하면, 그 다음 아스키코드 값이 나오는 것이 아니라, 다시 알파벳을 순회해야 한다. 따라서 원형 큐를 통해 풀어야겠다고 접근 2. 시행착오 문자열

1. 문제 접근 먼저 팰린드롬 가능/불가능 여부를 check하고 팰린드롬이 가능하다면, 문자열 처리를 통해 팰린드롬을 만든다. 이때, 홀수개의 문자열을 제대로 처리해야 한다. 2. 시행착오 여러 개의 출력이 나올 수 있는 팰린드롬 중 사전순서대로 가장 앞선 팰린드