https://www.acmicpc.net/problem/1342 1. 문제 요약 입력받은 문자열에 대해서 서로 인접해있는 문자가 같지 않은 문자열이면 행운의 문자열 이라고 한다. 문자열 내의 문자를 재배치하여 인접해 있는 문자가 서로 같지 않게 만들어 행운의 문자열이 몇개 나오는지 개수를 세는 문제 2. 알고리즘 (접근 방법) ○ 백트래킹 + DFS (재귀) 1. 해당 문자들을 재배치하기 위해서는 문자열내의 문자가 각각 몇개씩 있는지 셀 수 있는 카운트 배열을 두었다. char[] strArr = str.toCharArray();for(char ch : strArr) { int x = ch - 'a'; count[x]++;}입력받은 문자열을 문자 배열로 만들어준다. 반복문을 돌리..

https://www.acmicpc.net/problem/1005 1. 문제 요약특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간을 알아내는 프로그램 ※ 주의할 점 최소 시간을 알아내는 프로그램 이라지만, 동시에 건축을 해야하는 건물의 경우 그 건물들이 모두 건축이 완성되어야 다음 건물을 건축할 수 있기 때문에 최소 시간을 그리 신경쓸 필요 없는 듯 하다. 2. 알고리즘 (접근 방법) ○ 위상 정렬 방식 (Queue) 여기서 정점은 건축물을 말하는 것이며, 진입차수는 해당 건축물과 연결된 이전 건축물과의 간선이 몇개인지를 말하는 것이다. 1005번 사진에서는 1, 2, 3, 4 건축물들이 모두 정점임을 의미하고, 1번 정점이 3번 정점과 연결되어 있고 이를 간선이라고 표한다. 여기서 3번 정점..

https://www.acmicpc.net/problem/7785 1. 문제 요약출퇴근 로그를 통해 현재 회사에 있는 모든 사람을 구하는 프로그램 작성 ※ 주의할 점 현재 회사에 있는 사람의 이름을 사전 순의 역순으로 출력해야 한다. 2. 알고리즘 (접근 방법) ○ 첫번째 방식 (HashMap - Array.sort) 1. HashMap 을 이용하여, 직원 이름을 Key 값으로 삼고, "enter" 인 상태일 때만 HashMap 에 put 해주었다. 2. 기존에 "enter" 로 Map에 저장된 직원이 "leave" 로그로 입력받은 경우, 직원이름 Key 를 호출하여 해당 직원을 Map 에서 삭제 해주었다. 3. "enter" 로 Map 에 저장되어 있는 직원들의 이름이 역순으로 정렬해주..

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AYFofW8qpXYDFAR4 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 1. 문제 요약첫 날은 물을 준 나무의 키가 1 자라고, 둘째날은 물을 준 나무의 키가 2 자라고, 셋째날은 물을 준 나무의 키가 1 자라는 식. 홀수 번째 날은 키가 1자라고, 짝수번째 날은 키가 2 자란다. 모든 나무의 키가 가장 키가 컸던 나무의 키와 같아지도록 할 수 있는 최소 날짜 수 구하기 ※ 주의할 점최소 날짜 수를 구하기 위해 물을 안주는 날도 가능하다. 2. 알고리즘..

1439. 뒤집기 문제 링크 문제 접근 방식 1. 첫 인덱스의 값을 변수에 지정해둔다. 2. 첫 인덱스의 값과 다음 인덱스의 값이 같다면, +1 을 하지 않는다. 3. 첫 인덱스의 값과 다음 인덱스의 값이 다르다면, +1을 하고 변수의 값을 다음 인덱스 값으로 바꾼다. 4. 그렇게 1과 0의 연속된 값을 제거한 sum 중에 가장 적은 수가 최소 횟수가 된다. 연속된 값을 제거했다는 의미는 아래와 같다. 예를 들어,  0001100 이라는 숫자가 입력되었을 때 연속된 중복값을 제거하면 010 이 된다.여기서 0은 총 2개, 1은 1개다. 그래서 1이 0보다 적게 있기 때문에 1만 0으로 바꾸면 000이 되어 최소 한번만 뒤집어주면 된다. 11001100110011000001 가 입력되면 101010101 ..

이진탐색 이란 ? 범위의 절반인 50을 시도해가며 탐색하는 과정을 이진탐색이라고 합니다. 예를 들어, 100페이지인 책에서 70 페이지를 찾아가고 싶다고 가정했을 때 순차탐색의 경우, 1부터 70 까지 하나하나 1,2,3...68,69,70 이런 식으로 찾아가게 됩니다. 이진탐색의 경우,  100의 절반인 50을 찾은 후 타겟(70) 보다 작은 경우이기에 50~100 으로 범위를 변경하고50~100까지의 절반인 75를 찾습니다. 그리고 타겟보다 큰 경우이기에 50~75 로 범위를 다시 변경합니다. 이런식으로 절반씩 범위를 줄여나가는 것을 이진탐색이라합니다.  이진탐색을 통해 푼 무작위 수 찾기 문제코딩테스트 강의를 듣던 중 아래 문제를 푸는 과정을 기록하려합니다. 무작위 숫자로 되어있는 array 에서 ..

문제 요약 1. 정사각형의 각 변의 중앙에 점을 하나 추가한다. 2. 정사각형의 중심에 점을 하나 추가한다. 문제 풀이 오늘도, 선 정답 후 풀이를 하려 한다. 내가 푼 풀이는 아래와 같다. n = int(input()) print((1+(2**n))**2) 생각보다 단순한 코드였다. 먼저, 점의 개수가 늘어나는 규칙을 찾아본다면, 초기 -> 점 4개 N=1 -> 점 9개 N=2 -> 점 25개 N=3 -> 점 81개 이다. 이를 풀어서 작성한다면, 4 =2**2 9 = 3**2 25 = 5**2 81= 9**2 이렇게 된다. 그럼 여기서 알 수 있는 것은 사진에서 처럼 보이는 한 변의 길이만 구한 뒤, 정사각형의 넓이 구하는 형식(가로 * 세로)으로 풀면 점의 개수를 구할 수 있다는 것이다. 여기서 변..

진법이란? 0부터 n개의 숫자를 사용하여 수를 표현하는 방법으로 0~(n-1)만큼 표현한다. 수를 표기하는 기수법의 하나로 임의의 숫자를 사용하여 수를 표현하는 방법이다. 문제 요약 B진법 수 N이 주어지면 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하는 문제이다. 예를 들어, 10진법을 넘어가게 되면 알파벳 대문자를 이용하는데 A : 10, B: 11, ... ,Z : 35 처럼 알파벳 대문자는 각각 위의 숫자를 의미하게 된다. 문제 풀이 먼저 내가 푼 풀이를 공유하자면, 아래와 같다. import sys n,b = sys.stdin.readline().split() sum = 0 for i in range(len(n)) : # 0 ~ 문자열길이까지 if (n[(len(n)-1)-i].isdig..

Greedy (그리디) 란 ? 탐욕적인 뜻을 가진 Greedy(그리디) 는 탐욕법 이라고도 합니다. 이는, 현재 상황에서 지금 당장 좋은 것만 고르는 방법입니다. 풀어서 설명하자면, 그리디 알고리즘을 사용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘입니다. 그렇기 때문에 그리디 알고리즘으로 푼 답이 꼭 최적의 해가 아닐 수도 있다는 것입니다. 더보기 최적의 해란 구하고자 하는 답에 가깝거나, 문제풀이에 있어 정답인 해를 말합니다. 그렇다면, 최적의 해를 보장한다는 건 어떤 의미일까요? 먼저 가장 대표적인 그리디 알고리즘의 문제 예시로 거스름돈 문제풀이 방식을 확인해 보겠습니다. 문제 내용은 주어진 화폐단위 내에서 거스름돈의 동전을 최소한..

해시함수 란 ? 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 자료의 저장과 탐색에 쓰인다. 문제 요약 문제 a ~ z 까지 고유한 번호 1 ~ 26으로 부여해 준다. 입력받은 영어로 된 문자열을 고유한 번호로 바꿔준 뒤, 이 수열을 하나의 정수로 치환하기 위해 모든 수열을 더해준다. 그리고 다 더한 값을 유한한 범위를 갖기 위해 적당히 큰 수 M 으로 나눠준다. 이렇게 나오게 되는 것이 해시값이다. 하지만, 서로 다른 문자열이라도 동일한 해시값을 가질 수 있으며, 이를 해시충돌이라고 한다. 이러한 해시충돌을 줄이기 위해 수열의 각 항마다 고유한 계수를 부여하면 되는데 가장 대표적인 방법이 항의 번호에 해당하는 만큼 특정한 숫자 r을 거듭제곱해서 곱해준 다음 더하는 것이다. 이 문제에..