키자드에 등록된 총 263개의 포스트를 확인하실 수 있습니다.
문제 : https://programmers.co.kr/learn/courses/30/lessons/67256/solution_groups?language=python3$전체코드#파이썬 #python #python3
문제 : https://programmers.co.kr/learn/courses/30/lessons/67257#$핵심1. 패턴을 명시할 때, r 문자를 사용하는 것을 볼 수있다. ex)re.compile(r'(\d+)/(\d+)/(\d+)') r 문자는 raw string으로 백슬래시 문자를 해석하지 않고 남겨두기 때문에 정규표현식과 같은 곳에 유용하다. 예를 들어 r문자를 사용하지 않는다면ex)re.compile('(\\d+)/(\\d+)/(\\d+)') 와 같이 길어 백슬래시를 두 번 사용해야 하는 불편함이 있다. 그래서 보통 r문자를 붙여준다.2. permutations 사용 $전체코드#파이썬 #python
문제 : https://programmers.co.kr/learn/courses/30/lessons/67258$핵심투포인터 문제.처음에 풀었으나 효율성에서 떨어졌음. 이유를 살펴보니 딕셔너리를 무조건 사용해야 한다.딕셔너리는 자료구조 중에서 insert, delete 할 때 가장 시간복잡도가 적기 때문이다.$전체 코드#파이썬 #python
문제 : https://programmers.co.kr/learn/courses/30/lessons/67259$핵심-bfs-코너인지 직선인지 구분하는 것은 큐의 가장 마지막 값으로 구분할 수 있다. 큐의 가장 마지막 값과 앞으로 나아갈 값이 같다면 직선, 다르다면 코너이다.$전체코드#python
광고 없이 책 선정부터 공부해 온 과정, 순수 후기를 적어보려 한다. 정보처리기사는 2020년도부터 개편이 되었고, 코로나로 인해 한두 차례 연기되면서 나를 포함한 많은 수험생들이 준비를 하는데 어려움을 겪었다. 정보처리기사 시험을 준비하는 수험생이 본다면 큰 도움이 될 것이다.필기는 2020년 정기 기사 1,2회 통합을 응시하고, 실기는 2020년 정기 기사 2회를 응시했다.$ 합격증거0. 참고사항- 필자는 소프트웨어 전공 4학년에 재학 중인 학생이다. 1. 필기 준비필기점수 : 68점- 책 : <ncs 정보처리 기사 필기>책 + 시나공 모의고사로 준비했다. 아래 책으로 공부하고 시나공 모의고사를 하루 전에 여러 개.......
문제 : https://www.acmicpc.net/problem/11005$핵심숫자가 10이 넘어가면 11=A, 12=B, 13=C ... 로 변환해야 한다.ASCII코드를 이용하면 되므로A=65, B=66, C=67... 로 만들면 된다.그럼 숫자 10 이상이면, 숫자에 +55를 더해준다.$전체코드
문제 : https://www.acmicpc.net/problem/2529$핵심재귀 함수 - 백트래킹 을 이용해서 풀었다.스택을 이용했으면 더 편하고, 더 빠르고 간결하게 짤 수 있었을텐데좀멍청했던 것 같다. 하지만 재귀함수를 처음 구현해 본 문제였기에 의미가 있었다.$전체코드
문제 : https://www.acmicpc.net/problem/2804$핵심2중 for문을 돌릴 때 주의해야 한다.A(i)를 기준으로 B(j)를 돌려 검사해야 A에서 가장 먼저 등장하는 글자를 선택할 수 있다.혹시모를 반례 테스트케이스$전체 코드
문제 : https://www.acmicpc.net/problem/1212$핵심처음에 2진수->10진수->8진수로 짜다가 " 주어지는 수의 길이는 333,334을 넘지 않는다." 를 보고 다른방법을 찾아보았다. 수가 333,334가 아니라 길이였다. ㅋ8진수->2진수로 바로 변환하는 법이 있다.세자리의 2진수는 1자리의 8진수와 동일하다."2진수 100" 은 "8진수 4" 이다.그렇다면 미리 배열을 이용해 0~7까지의 8진수 숫자를 0~111의 2진수 수로 변환해 놓으면 된다.s1 배열 : 0~7의 8진수를 0~111 까지의 2진수로 변환했다.s2 배열 : "반드시 1로 시작해야 한다."라고 했으니, 앞의 "0"을 모두 제거해 주면 된다.str.......
문제 : https://www.acmicpc.net/problem/14501$핵심퇴사 하기 전까지 상담을 통해 최대로 받을 수 있는 비용을 구하는 문제.현재(i) + 상담에 걸리는 날(a[i][0]) 이 n 이하일때 점화식을 통해 dp를 갱신한다.$핵심 점화식dp[i+a[i][0]] = max(dp[i]+a[i][1],dp[i+a[i][0]])$간과할 수 있는점.다음 값을 최댓값으로 계속 갱신해야함.$전체 코드
문제 : https://www.acmicpc.net/problem/2981$핵심arr에 입력받은 수들을 오름차순으로 정렬한다.1.(arr[i]-arr[i-1]) 의 최대공배수(m)를 구한다.2.최대공배수(m)의 약수들을 출력한다.3.출력할 때 아래와 같은 형식으로 출력할 때에는 Console.Write("{0} ",i); 으로 출력한다.$유클리드 호제법에 의한 최대공약수 구하기$전체코드
문제 : https://www.acmicpc.net/problem/2839$핵심 5로 나누었을때 나머지가 0일때가 많아야 최솟값을 얻을 수 있다.1. 5로 나누었을때 나머지가 0이라면, 나눈 몫을 결과값(cnt)에 더해준다.2. 5로 나누었을때 나머지가 0이 아니라면, 입력값에 -3을 해주고 결과값(cnt)을 1 증가시킨다.3. 이를 반복한다.4. 원하는 결과가 나왔을 때(모든 설탕을 봉지에 담았을 때) 결과값을 출력한다.5.그렇지 않다면 -1을 출력한다. $전체코드
문제 : https://www.acmicpc.net/problem/1676$핵심2x5의 개수가 0의 개수를 좌우한다.$전체코드
문제 :https://www.acmicpc.net/problem/10825$핵심- c#에서 정렬은 .netFramework 가 제공하는 쿼리함수를 이용한다.-우선 구조체로 학생들의 정보를 담고, 학생들을 List에 담는다.Orderby(s => s.a) : a변수에 대해 오름차순 정렬OrderByDescending(s=> s.b) : b변수에 대해 내림차순 정렬ThenBy : 다중 오름차순 정렬. OrderBy에 이어붙임.$전체코드
문제 : https://www.acmicpc.net/problem/2581$ 핵심-에라토스 테네스의 체를 이용해 구했다.참고 : https://blog.naver.com/hands731/221883892922$ 전체코드
문제 : https://www.acmicpc.net/problem/1111예전에 신경망 가중치 공부할 때 비슷한 느낌이 나는 문제였다.규칙을 찾아서 다음에 올 수를 예측하는 문제이다.$ 핵심- 다음 수가 1개일 때의 규칙은 입력된 수가 3개이상일 때 가능하다.- 규칙은 다음과 같다 => (구하고자 하는 수) = (앞 수) x tempA + tempB 에서 tempA = (a2 - a1) / (a1-a0) tempB = a1 - tempA x a0$전체 코드]
문제 :https://www.acmicpc.net/problem/16396bool 배열을 이용해서 풀었음.$ 전체코드
문제 : https://www.acmicpc.net/problem/2908$핵심string -> reverse(char) -> char[] -> string -> int$전체코드(c#)
문제 : https://www.acmicpc.net/problem/10809해결 : ascii코드로 변환한 후, 딕셔너리 key(ascii코드)에 맞는 인덱스 번호를 넣어주었다.$char to ascii$ 딕셔너리 foreach로 key, value 추출하기 $전체코드(c#)
문제 : https://www.acmicpc.net/problem/1934c# 에서 최소 공배수와 최대 공배수 따로 모듈함수를 지원하지 않는다.직접 사용자 정의 함수를 만들어 보자.$ 최소 공배수lcm : 최소 공배수, gcd : 최대 공배수식 lcm = (AxB)/gcd(A,B) 을 이용한다. 그럼 최대공약수만 구할 줄 알면 된다.$ 최대 공약수$전체코드#최대공배수
문제 : https://www.acmicpc.net/problem/10866$핵심그냥 리스트를 이용하면 시간초과가 난다. StringBuilder 를 이용해서 출력해 주어야 한다.$참고딕셔너리를 이용해 큐를 구현하였음.fc = front cursor (front 인덱스 번호) bc = back cursor (back 인덱스 번호)$ 전체코드
문제 : https://www.acmicpc.net/problem/10845$핵심1.자료구조 Queue사용.2.StringBuilder 이용해 출력.$전체코드(c#)
문제 : https://www.acmicpc.net/problem/9095$핵심dp문제.n=1일때, 1n=2일때, 1+1, 2n=3일때, 1+1+1, 1+2, 2+1n=4일때, 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3규칙을 살펴보면, 다음과 같은 점화식을 정의할 수 있다.dp[4] = dp[1]+dp[2]+dp[3]$전체코드(c#)
문제 : https://www.acmicpc.net/problem/1110$핵심do while 문을 돌면서 조건이 만족할 때까지 돈다.입력받은 string -> char[] -> int 로 변환해 각자리 숫자를 합하고, 결과값의 가장 오른쪽자릿수 구한다.입력받은 수의 가장 오른쪽 자릿수를 구한다.$전체코드(c#)
문제 : https://www.acmicpc.net/problem/11655$핵심string -> (int)ASCII 로 변환 후 13을 밀면된다.변환은 "(int)a" 로 간편하게 변환 가능하다.이때, z를 넘어가면 다시 a부터 센다.대소문자를 구분하기 때문에, c#에서 지원하는 IsUpper()메서드 이용해서 대문자를 구분한다.$전체코드
문제 : https://www.acmicpc.net/problem/10798$핵심2차 배열을 만든 후 세로로 읽어들이면 된다.-2차원 배열 만들기. (char[]) 형$전체코드
문제 : https://www.acmicpc.net/problem/11057$핵심dp문제 이므로 규칙을 파악한다.빨간색 글씨가 서로 같은것을 볼 수 있다.노란색 부분 : 55-10 = 45 45-9 = 36$전체코드
문제 : https://www.acmicpc.net/problem/1541$핵심주어진 문자열 : "55-50+40"답 : -35주어진 문자열을 분해해야 한다. 1. 먼저 "-"로 분할한다.2."+" 로 분할한다.3. 분기 처리를 잘 해준다. 3-1. "-"를 포함 할때 or 포함 안할때3-2. "+"를 포함 할때 or 포함 안할때$주의할점"가장 처음과 마지막은 숫자이다"-> 맨 앞에 "-"가 오지 않는다!$전체코드 (c#)
문제 : https://www.acmicpc.net/problem/1037$핵심1. 1과 n(자기자신)을 제외한 약수의 개수(진짜 약수) 가 1개일 경우 : (진짜 약수) x 22. 그렇지 않을 경우 : (가장 큰 진짜 약수) X (가장 작은 진짜 약수)$전체 코드
문제 : https://www.acmicpc.net/problem/2675$핵심Console.Write 를 남발했지만, 시간복잡도가 커진다.StringBuilder를 강력 권고한다.나는 귀찮아서 Console.Write를 사용하였다.$전체코드
$ 8593번 (c#)문제 : https://www.acmicpc.net/problem/8393$ 10952번 (c#)문제 : https://www.acmicpc.net/problem/10952
$ 2588번 곱셈 : (c#)문제 : https://www.acmicpc.net/problem/2588$2562번 : 최댓값(c#)문제 : https://www.acmicpc.net/problem/2562
$10039번 평균점수 (c#)문제 : https://www.acmicpc.net/problem/10039$ 2753번 : 윤년 (c#)문제 : https://www.acmicpc.net/problem/2753
$8958번 OX퀴즈 (c#)문제 : https://www.acmicpc.net/problem/8958$ 2750번 : 수 정렬하기 (c#)문제 : https://www.acmicpc.net/problem/2750
$전체동작- FUP(File Upload Protocol) 를 직접 설계하고, 서버와 클라이언트를 구현한다. 서버와 클라이언트에서 사용하는 공용 클래스 라이브러리(Send메서드, Receive메서드)를 사용자 정의한다.- 클라이언트에서 파일을 전송하면 서버에 파일이 업로드된다.1.동작$. FileSender(클라이언트) 폴더- 업로드할 파일 : photo.jpgDebug파일 아래 둔다.$. FileReceiver(서버) 폴더- 지금은 비어있고, 나중에 서버에 "photo"파일이 업로드가 될 것이다.$.FileSender(클라이언트)입력 : FileReceiver upload-> 서버가 시작된다.입력 : yes->파일 업로드 요청을 수락하면서 파일 전송을 시작한다."##...(생략).........
문제 : https://www.acmicpc.net/problem/11052카드 n개를 구마하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제.n=4일때dp[0]=arr[0]dp[1]=max (dp[0]x2, arr[1] )dp[2]=max (dp[1]+dp[0],arr[2]) => max (dp[2],dp[1]+dp[0])dp[3]=max (dp[2]+dp[0],arr[3]) => max(dp[3], dp[2]+dp[1]) => max(dp[3], dp[1]+dp[2])...점화식$전체코드
문제 : https://www.acmicpc.net/problem/2565LIS(최장 증가 수열) 응용문제.두 전봇대를 비교하다가 오른쪽 전봇대의 수가 더 작으면 dp에 1을 증가시킨다.$전체코드
문제 : https://www.acmicpc.net/problem/14501퇴사 하기 전까지 상담을 통해 최대로 받을 수 있는 비용을 구하는 문제.현재(i) + 상담에 걸리는 날(a[i][0]) 이 n 이하일때 점화식을 통해 dp를 갱신한다.$핵심 점화식dp[i+a[i][0]] = max(dp[i]+a[i][1],dp[i+a[i][0]])$전체코드
문제 : https://www.acmicpc.net/problem/2822tuple List를 이용해 풀었다.$.tuple listList<Tuple<int,int>> list = new List<Tuple<int,int>>();$.tuple sort(Item2 기준 내림차순)list.Sort((a,b) => b.Item2.CompareTo(a.Item2));$.tuple 요소 접근Item1, Item2 로 접근.$전체 코드
문제 : https://www.acmicpc.net/problem/2577딕셔너리 사용해서 풀었다.#딕셔너리 선언Dictionary<int,int> dict = new Dictionary<int,int>();#temp를 int -> string -> int -> dictionary 로 변환해서 저장했다.주의 할 점은 string의 index를 쪼갤때 다시 ToString()으로 변환해 주어야한다.$전체코드 (c#)
문제 : https://www.acmicpc.net/problem/3052$핵심c#에서 중복제거 방법은 두가지가 있다.1. IEnerable 사용 (메모리 높고, 시간 짧다)2.HashSet 사용 (메모리 낮고, 시간 길다)-HashSet의 Add 메서드는 중복된 값이 없어 성공적으로 추가될 경우 true를 return하고, 중복된 값이 있을경우 false를 return한다.$전체코드
문제 : https://www.acmicpc.net/problem/7562BFS문제$ 전체 코드#python
문제 : https://programmers.co.kr/learn/courses/30/lessons/64063$핵심k가 10의 12제곱 이하인 자연수이고, room_number의 크기가 20,0000 이기 때문에 리스트를 미리 만들어 초기화 시켜주는 것은 매우 비효율 적이다. 이 문제에서는 효율성 테스트를 가지고 있으므로, dictionary를 이용하고, union-find(유니언 파인드)를 응용해야만 풀 수 있다.$전체코드#python #인턴십
문제 :https://www.acmicpc.net/problem/2583$전체코드#python
문제 : https://www.acmicpc.net/source/19515205$슬라이딩 윈도우작동방식이 마치 미닫이 창문 같다고 해서.리스트에서 max값을 구할때는 한개의 값이 필요하고, 피보나치 수열을 구할때 3개의 값이 필요하다. 모든 이전의 값들은 필요가 없다.동적 계획법을 짜다가 메모리 초과가 나는 경우가 있는데, 이 기법으로 해결할 수 있다.$전체 코드#python
문제 : https://www.acmicpc.net/problem/11003슬라이딩 윈도우 문제$나의풀이deque로 push, pop 해야되겠다는건 생각했다. 오랜시간 maxlen이 머리속에 지워지지 않았고, 뭔가 사용해야 될것같은 똥고집이 생겨버렸다. 오래걸렸지만, 핵심은 while문을 사용해 조건에 부합하는 값들을 que에서 지워주는 것이다.$전체코드#python
문제 : https://programmers.co.kr/learn/courses/30/lessons/64064$핵심1. 정규표현식 사용할 때 패턴에 항상 '^'(텍스트 시작지점) 과 '$'(텍스트 종료지점)을 작성하자.2. 집합(lst)은 항상 mutable(변경가능한) 하기 때문에 copy()로 복사를 해주자.3. dfs - 백트래킹 이용.$전체 코드#python #인턴십
문제 :https://programmers.co.kr/learn/courses/30/lessons/64062$메모이분탐색 문제.투포인터 문제인줄 알고 삽질했다.나중에 이분탐색과 투포인터의 차이점과, 사용시기에 대해서 정리해봐야 겠다.$ 전체코드#python #인턴십
문제 : https://programmers.co.kr/learn/courses/30/lessons/17680문제를 이해하기 위한 용어 설명$ cache hit, cache miss-cache hit : 찾으려는 데이터가 이미 캐시되어 있다면 발생. 메인 메모리를 거치지 않고 빠르게 데이터를 불러올 수 있다.-cache miss : 데이터가 캐시되어 있지 않다면 발생. 이미 가득찬 캐시에서 cache miss가 발생하면 캐시의 교체정책에 따라 다른 캐시된 데이터를 추출하고 지금 불러오는 데이터를 캐시한다.$ LRU(Least Recently Used)-가장 오랫동안 참조되지 않은 페이지를 교체하는 기법ex) cache size : 3, cities : [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul]$ 전체코드collec.......
문제 : https://www.acmicpc.net/problem/2529그리디 문제.백트래킹 이용$전체코드#python
문제 : https://programmers.co.kr/learn/courses/30/lessons/42888$핵심딕셔너리(name)을 생성하고, Enter,Change가 발생할 때 key=userid value=닉네임을 갱신해준다.$전체코드#python #카카오
문제 : https://programmers.co.kr/learn/courses/30/lessons/17679$전체코드
문제 : https://programmers.co.kr/learn/courses/30/lessons/42890$코드
문제 : https://programmers.co.kr/learn/courses/30/lessons/60059#[[0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0],[0, 0, 1, 1, 1, 0, 0],[0, 0, 1, 1, 0, 0, 0],[0, 0, 1, 0, 1, 0, 0],[0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0]](0,0) (0,1) (0,2) (2,0) (1,0) (0,0)(1,0) (1,1) (1,2) (2,1) (1,1) (0,1) (2,0) (2,1) (2,2) (2,2) (1,2) (0,2)[[0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0], [0, 1, 2, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]][[0, 0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0], [0, 1, 3, 2, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 1,.......
문제 : https://programmers.co.kr/learn/courses/30/lessons/64061$핵심주어진 2차원 배열(board)를 뒤집어야(?)한다.$전체코드#python
문제 : https://programmers.co.kr/learn/courses/30/lessons/64065$핵심1. 입력이 문자열로 주어졌다. 문제에서는 집합이라고 하더니, 자세히보니 문자열이었다. 입력의 형식을 꼭 확인하자.$전체코드
문제 : https://level.goorm.io/exam/43210/%EC%A2%8B%EC%9D%80-%EC%88%98%EC%97%B4/quiz/1백트래킹 문제$ 전체 코드#python
문제 : https://level.goorm.io/exam/43263/%ED%8A%B9%EC%A0%95-%EA%B5%AC%EA%B0%84%EC%9D%98-%ED%95%A9/quiz/1dp로 푸라고 하였으니 dp로 풀어보겠다.$ 전체코드dp로 안풀고 더 간단하게 풀 수도 있다.그냥 .. 단순 계산하면 된다.$추가 코드
문제 : https://level.goorm.io/exam/43230/%EA%B0%9C%EA%B5%AC%EB%A6%AC-2/quiz/1dp문제$전체 코드#python
문제 : https://level.goorm.io/exam/43260/2%EA%B0%9C%EC%9D%98-%EA%B3%84%EB%9E%80/quiz/1문제가 무슨말인지 몰라서 검색해 보았다.참조 : https://johngrib.github.io/wiki/two-eggs-100-floor/여러가지 방법이 있을건데, 우리가 원하는 것은 최소한의 실험횟수의 worst case가 나오게 해야한다.그럼 횟수를 제한하는 방법을 사용해야 한다.-만약 횟수를 10회로 제한했을때10 층에 가서 1번 계란을 떨어뜨려 본다. (남은 횟수 9)깨졌다면 2번 계란을 써서 1 ~ 9 층을 대상으로 한 층씩 올려가며 선형 탐색을 한다.1번 계란이 안 깨졌다면 19 층에 가서 떨어뜨려 본다. (남은 횟수 8)깨졌다면 2번 계란을 써서 11 ~ 18 층을 대상으로 한 층.......
문제 : https://level.goorm.io/exam/43211/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-dijkstra-s-algorithm/quiz/1dijkstra Algorithm1.다익스트라 알고리즘-출발node에서 최종node까지 모든 node가 선택될 때까지 반복한다.(가중치의 합이 가장작은 정점을 계속해서 선택한다)-BFS(너비우선탐색)를 기반으로 탐색하기 때문에 que를 사용한다.-단일 정점에서 원하는 도착지까지 최단 경로를 구할 수 있다.결론 : 시간복잡도는 O(V^2)이다. 시작 정점에서 최종 정점까지 최단거리를 구한다.*파이썬 코드1.graph[a]=(b,c) : a에서-->b까지 가중치는 c이다 (a,b는 노드)2.result[a] : start에.......
문제 : https://level.goorm.io/exam/43064/binary-search/quiz/1binary search(이진 탐색) - 시간(O(logn))오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 검색 속도가 아주 빠르다.정렬된 자료를 반으로 나누어 탐색하는 방법, 반드시 자료는 오름차순 으로 정렬한 상태로 시작해야한다. 로그실행시간을 보장한다.이진탐색과 순차탐색의 비교.step수를 보면 탐색 시간을 절약할 수 있는것을 볼 수 있다.https://blog.penjee.com/binary-vs-linear-search-animated-gifs/ 이분 탐색 문제$ 전체코드#python
문제 : https://www.acmicpc.net/problem/13397간만에 기가막힌 문제를 만났다.노트북을 향해 1분정도 엄지를 치켜세웠다.이분탐색 응용문제이다.$핵심문제에서 요구한 것은 각 구간의 "(최댓값-최솟값)" 의 최댓값 중 최솟값을 구하는 것이다.말이 어렵다 ㅇㅅㅇ고로, 이분탐색 기준값(mid)는 각 구간의 (최댓값-최솟값) 의 최댓값 중 최솟값으로 정의(이후 result라 부른다)할 것이다.divide(x)함수는 인자인 x가 mid값이고, 투 포인터 알고리즘을 구현했다.변수 max_x : 구간에서 가장 큰 값변수 min_x : 구간에서 가장 작은 값(max_x - min_x)의 값이 result 보다 크다면, 구간이 하나 만들어지게 된다.(cnt+=1)return .......
문제 : https://www.acmicpc.net/problem/3986스택문제문제를 이해하는데 오래걸렸다$문제설명-문제의 내용을 가져와봤다.1. 만약 선끼리 교차하지 않으면서-안되는 문자열 : 'ABAB', 'BABA' -되는 문자열 : 'AABB', 'BBAA'2.각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면-되는 문자열 : 'ABBA' , 'ABBBA'$ 문제풀이앞에서부터 스택에 하나씩 넣어서 같은 글자가 붙어있으면 pop시키고, 다른 글자면 push한다.마지막에 stack이 비어있으면 좋은단어이다.$ 전체코드
문제 : https://level.goorm.io/exam/43082/%EC%B5%9C%EB%8B%A8-%EA%B1%B0%EB%A6%AC-%EA%B5%AC%ED%95%98%EA%B8%B0/quiz/1$ 핵심최단거리 -> bfs문제$ 전체코드#Goorm #python
문제 : https://www.acmicpc.net/problem/10775유니온 파인드(union find)문제이 문제를 유니온 파인드로 생각하는게 관건.(시간 복잡도때문에 유니온 파인드가 적격)$핵심parent 배열은 v 항공기가 갈 수 있는(가능한) 게이트(부모)를 저장한 배열.ex) 처음 4번 비행기가 들어오면, 4번자리에 비행기가 도킹할 것이고, parent[4]=3 으로 바꿔줌 으로써 다음 4번 비행기가 들어오면 3번 자리에 도킹을 안내해 준다.$전체코드#python
문제 : https://www.acmicpc.net/problem/1725스택 문제$핵심cursor : 현재 x좌표 값 (나중에 (i-cursor) 이용해서 가로 길이를 구한다.)stack : 튜플 (x좌표값, 높이) 를 저장하는 스택 $ 전체 코드
문제 : https://www.acmicpc.net/problem/4195유니온 파인드(union-find) 알고리즘 이용.아래와 같은 Tree구조로, {1, 2, 5, 6, 8}, {3, 4}, {7}의 경우에는 아래처럼 구현이 가능할때 사용.최상단 노드인 Root노드를 ID로 사용하고, 자식 노드들이 root를 찾아갈 때 사용.주어진 두 원소 또는 집합을 합하해 Tree구조를 만드는 Union부분과 root를 찾아가는 Find함수로 이루어져있다.
문제 : https://www.acmicpc.net/problem/1976$dfs로 푼 코드$union-find(유니온 파인드)로 푼 코드
문제 : https://programmers.co.kr/learn/courses/30/lessons/12936n명을 총 줄세우는 방법은 n!입니다. 예를 들어서 위와 같은 3명을 줄을 세우면 3!가지가 전체 줄을 서는 경우의 수입니다. 잘 살펴보면, 각 사람들이 첫 번째에 있을 경우 2가지입니다.(1번 사람이 첫 번째에 있을 경우 2가지, 2번 사람이 첫 번째에 있을 경우 2가지, 3번 사람이 첫 번째에 있을 경우 2가지) 이를 수식으로 살펴보면 각 사람이 첫 번째에 올 경우의 수는 (n-1)!과 같습니다. 이것을 이용하여 한자리씩 구해나가면 됩니다! 따라서 k를 (n-1)!로 나누면, k번째 방법에 어떤 수가 가장 앞에 있는지 알 수 있습니다. 나눈 몫은 숫자를 구하는데 사용하고, 나머지는.......
처음에 커서를 움직이는 방식으로 문제를 풀었지만, 시간복잡도가 너무 커졌다. 아마 연산의 갯수가 두배정도 많아서 그런것 같다.따라서, 커서를 그대로 두고 문자열을 움직이도록 하는 것을 생각할 수 있습니다. 입력된 문자를 리스트에 담도록 합니다. 만약 커서를 움직여서 왼쪽으로 이동하게 되면 리스트 요 소들을 pop시킨 후 다른 리스트에 담아 놓으면 됩니다. 즉 커서를 기준으로 양쪽에 리스트가 있다고 생각하면 됩니다.$전체코드
문제 : https://www.acmicpc.net/problem/10799스택(변수)을 활용한 문제$내코드$다른사람 코드
문제 : https://www.acmicpc.net/problem/6236사실상 이분탐색 문제.$핵심if mid<money[i]:-만약 mid(인출할 수 있는 최소금액) 가 money[i](이용할 금액) 보다 낮을경우 flag를 줘서 따로 처리해주어야 한다.$전체 코드
문제 : https://www.acmicpc.net/problem/7453이 문제가 왜 이분탐색 문제이지? 하고 의문이 들었던 문제.문제 처음읽었을때 설마,, 배열두개씩 묶어서 AB, CD를 따로 구하고 계산하면 시간복잡도가 절반으로 떨어질거 같은데,, 라고 생각했는데 그렇게 푸는게 맞았다..어이없었던 문제.파이썬의 장점을 이용해서 dictionary의 key에 값을 저장하고, value에는 값의 개수를 저장한다.
문제 : https://www.acmicpc.net/problem/10815파이썬으로 이 문제는 이분탐색으로 안풀어도 된다.이분탐색 문제이므로 이분탐색으로 풀었다.
문제 : https://www.acmicpc.net/problem/1072$문제 핵심1.종료조건을 잘 생각하자.-승률이 99프로 이상인 경우는 -1 return-end를 잘 설정하다.(문제의 최대 범위만큼) ->맨날 멋부리다가 뇌절함 $전체모드
문제 : https://www.acmicpc.net/problem/3020누적합 알고리즘 이용.누적합 알고리즘 자체는 어렵지않다. 하지만, 이 문제가 어렵다..누적합 변수를 mid로 두었다. mid에 누적하면서 부신 벽의 최소 갯수를 구한다(minn). mid 의 초기값은 mid= n//2 이다.-> 벽은 양수이기때문에 1m구간에 최소 n//2 개의 벽이 존재한다.(석순 o 종유석 x)-> 또, 누적합을 할때 1m구간부터 시작하기때문에 초기값 mid=n//2huddle 배열 : huddle[i]는 (i+1)m 높이에서 n//2를 기준으로 추가된 벽의 수이다. ->ex) n=2이고, huddle[2]=1 이면, (2+1)m에서 부시는 벽의 개수는 총 : 두(1+1)개이다. huddle배열에 벽을 저장해.......
문제 : https://www.acmicpc.net/problem/5052$핵심-list sorting 할때 문자열로 된 숫자들의 sorting이 내가 기존에 알고있던 방식과 달랐다! 미래의 멍청한 실수를 알아차릴 수 있는 좋은 문제였다.-아래와 같은 정렬이 일어난다.-각 요소의 자릿수와 상관없이 1.가장 앞 자리의 숫자부터 비교한다. 2.똑같으면, 그 다음으로 길이를 비교그래서 2중 for문도 필요가 없다. $전체코드
문제 : https://www.acmicpc.net/problem/11376유사문제 : 열혈강호열혈강호 문제에서 2줄추가했다. 직원 한명이 일 두개를 처리할 수 있다고 한다.이분매칭.$전체코드
매우 유용한 내용이라 나중에 꼭 다시 찾아볼 것 같다.https://koosaga.com/18알고리즘 증명https://koosaga.com/133
문제 : https://www.acmicpc.net/problem/1671이분매칭 풀이.$핵심1. 이분매칭을 사용하기 위해서는 이분그래프가 성립되야 한다. i번째 상어가 먹을 수 있는 요소들을 배열로 만든다-풀이에서는 target변수에 해당.2. dfs()를 두번 돌린다.$전체코드pypy3
$분할 정복1.병합 정렬(merge sort)-1.문제를 계속해서 반으로 자르고 2.재귀를 통해 각각 정렬하고 3.다시 합병시키는 정렬. -유의사항 : list는 muttable 객체이기 때문에 함수 인자로 받아서 변경하면 변경됨.2.퀵정렬-1.기준값(pivot)을 기준으로 작은값은 왼쪽리스트, 큰값은 오른쪽 리스트로 나누고 2.하나 이하로 남을때까지 재귀로 반복한다. 3.다시 합병시킨다.3. 선택 정렬-현재 선택된 데이터 이후의 정렬 되지 않은 데이터 중에서 가장 작은(혹은 가장 큰) 데이터를 선택해 현재의 데이터와 위치를 교환하는 방식으로 정렬되는 방식이다. -시간복잡도 : O(N^2)-최근접 점의 쌍 문제최대 부분합 문제정렬별 장단점과 시.......
문제 : https://www.acmicpc.net/problem/117291. n==2 일때까지 재귀를 한다.2. ret에 저장 후 출력을 통해 가장 큰 원반을 옮긴다.(from -> to)3. 나머지 원반을 to로 옮긴다.
문제 : https://www.acmicpc.net/problem/1992최소단위까지 분할해서 계산한다.$내풀이len(r1) == 1 : 최소단위에서만 return할 내용 $다른사람풀이set을 이용한 "파이썬스러운" 코드.$ t[0] in ('0','1') 써줘야 하는 이유
문제 : https://www.acmicpc.net/problem/1074가능한 범위가 n==15일때 이니 재귀호출이 무수히 많이 일어나 시간초과가 빈번하게 일어난다.이를 해결하기 위해 조건을 하나 더 걸어준다.$핵심범위내에서 답이 있지 않으면, 더이상 재귀호출을 하지 않고, 넓이 합을 return시킨다.+정석적으로 한다면 재귀의 depth가 10까지 들어가지만, r과c가 범위내에 없으면 depth 2에서 depth 10까지의 결과를 모두 계산해서 return한다.#파이썬 #python
문제 :https://www.acmicpc.net/problem/1780$핵심set 사용해서 "파이썬 스럽게" 짜봤다.step에 9방향 좌표를 입력해 중복코딩을 방지한 것이 특징이다.$전체코드#파이썬 #python
문제 : https://www.acmicpc.net/problem/2630$핵심set 사용해서 "파이썬 스럽게" 짜봤다.step에 4방향 좌표를 입력해 중복코딩을 방지한 것이 특징이다.$전체코드#파이썬 #python
문제 : https://www.acmicpc.net/problem/6549stack을 이용한 풀이.$핵심arr : stack. (cur,n[i])요소로 구성. 지속된 너비(cur)와 현재(i) 높이(n[i])저장. 높이가 감소하면 pop. $전체코드
문제 : https://www.acmicpc.net/problem/6086에드몬드카프 알고리즘 사용.$에필로그아마 구글링을 하면 에드몬드 카프 알고리즘을 이용한 풀이에 대한 정보가 제한적일 것이다.실제로 파이썬으로 푼 사람이 얼마 없었다.따라서 다른 포스팅에서 자바 코드로 공부한 뒤 파이썬으로 풀어보았다.문제에 대한 파이썬 코드 설명을 중점으로 하기 때문에 에드몬드 카프 알고리즘과 네트워크 플로에 대해서는 별도로 공부하고 오는 것을 추천한다.$변수(or 함수) 설명- h : 람다 함수. 알파벳을 ASCII 코드로 변환하는 ord() 함수 이용. ex) A->0, B->1, C->2- c : 유량 용량. 양방향으로 저장해 준다.- f : 현재 흐르는 유량.- adj :.......
맨날 검색해서 찾아보기 귀찮아서.. 저장.출처 : https://blog.naver.com/yhol98/221606311437
문제 : https://www.acmicpc.net/problem/2188네트워크 플로우의 하나인 이분 매칭 문제이다.$이분 매칭(Bipartite Matching)이란? -각 용량을 1로 설정한 네트워크 플로우 문제.-이분 그래프에서 A 그룹의 정점에서 B 그룹의 정점으로 간선을 연결 할 때, A그래프의 하나의 정점이 B그래프 하나의 정점만 가지도록 구성된 것이 이분 매칭이다.$ 이분 그래프(Bipartite Graph)란?-정점을 두개의 그룹으로 나누었을 때, 존재하는 "모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태"의 그래프를 의미한다.$ 축사문제 흐름$변수설명-dfs(x) : x(i번째 소) 번호 소가 들어갈 축사를 찾는 함수. True-안착할 축사를.......
문제 : https://www.acmicpc.net/problem/11375이 문제의 시간복잡도를 최적화 시키기 위해서는 호프크로프트 알고리즘으로 풀어야 한다.한시간동안 포스팅 찾아보면서 열심히 공부했지만 현타가 와버렸다.내가 무엇을 위해 생전 처음보는 알고리즘인 호프크로프트 알고리즘을 열심히 공부하고 있는지 의문이 들었다.결론 호뭐시기 알고리즘은 제끼고 이분매칭을 사용했다.알고리즘 공부를 단순히 취업을 위해서 간단히 공부한다는게 너무 멀리 와버린 느낌도 들었다.아무튼 시간복잡도는 우수하지 않지만, 그래도 풀 수 있다는게 어디인가!나중에 시간이 허락된다면 다시 돌아오겠다. 그럼 2만$전체코드