옌의 로그

문제[프로그래머스] 단어 변환 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사용 알고리즘- BFS (너비우선탐색) / 그래프 탐색- 시간복잡도 O(N² × L) (N: 단어개수, L: 단어길이) 해결방법단어 배열에 타겟이 있는지 체크 후, 없다면 바로 종료(return 0)해준다각 단어를 노드로 보고, 한 글자만 다른 단어를 간선(edge)으로 연결해 그래프를 먼저 만든다begin과 한 글자 차이나는 단어들을 시작 노드로 보고 큐에 먼저 넣은 후 BFS를 돌린다BFS는 가까운 단어부터 탐색하므로, 타겟 단어에 처음 도달한 시점의 단계 수가 곧 최단 변환 횟수가 된다소스코드사용언어 : javaimport ja..

문제[프로그래머스] 숫자 게임(Summer/Winter Coding(~2018))사용 알고리즘- 투 포인터 (two pointer) / Greedy- 시간복잡도 O(N logN)해결방법A, B를 모두 오름차순 정렬A의 각 원소에 대해, B에서 A보다 큰 숫자를 찾아 이긴 횟수를 증가시킨다소스코드사용언어 : javaimport java.util.*;class Solution { public int solution(int[] A, int[] B) { int answer = 0; // A, B 오름차순 정렬 Arrays.sort(A); Arrays.sort(B); int j = 0; // B inde..

문제[프로그래머스] 야근 지수사용 알고리즘- Heap / Greedy- 우선순위 큐 (PriorityQueue)- 시간복잡도 O(n logN) (n: 남은 시간, N: 작업 수)해결방법주어진 works를 우선순위 큐에 작업량이 많은 순으로(내림차순) 넣는다남은 작업시간 n 동안 반복문을 돌면서, 가장 많은 작업량을 가진 일을 찾아서(조회) 1씩 줄이고 다시 큐에 넣는다이 동작을 효율적으로 처리하기 위해 힙 구조를 사용소스코드사용언어 : javaimport java.util.*;class Solution { public long solution(int n, int[] works) { long answer = 0; PriorityQueue pq = new PriorityQueu..

문제[프로그래머스] 추석트래픽(2018 KAKAO BLIND RECRUITMENT)사용 알고리즘- 윈도우 슬라이딩해결방법각 로그의 종료 시각과 처리 시간을 이용해 시작~종료 구간을 밀리초 단위 Interval로 변환한다.모든 로그 구간을 리스트에 저장한다. logList각 로그의 종료 시각을 기준으로 [end, end+999] 윈도우를 만들고, 이 구간과 겹치는 로그 개수를 센다.모든 윈도우에서의 최대 겹침 개수를 정답으로 반환한다.더보기- 연속된 구간(subarray, substring 등)을 효율적으로 탐색하거나 계산할 때 사용하는 알고리즘 기법- 핵심은 고정된 크기(또는 가변 크기)의 윈도우를 데이터 위에 올려두고, 한 칸씩 "밀면서(slide)" 계산을 이어가는 방식 개념 정리윈도우(Window)..

문제[프로그래머스] 연속 펄스 부분 수열의 합 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사용 알고리즘- Kadane's algorithm> 연속 부분수열(부분배열)의 최대 합을 O(n)에 구하는 전형적인 DP/그리디 기법해결방법주어진 수열을 돌면서 연속 합이 0보다 작아지면, 더하지 않고 새로 합계를 시작한다pulse를 적용하기 위해 1, -1을 가지는 배열을 전체적으로 감싸 수열의 값마다 펄스를 곱해서 처리 *Kadane algorithm더보기i번째 원소까지 봤을 때maxEndingHere = i에서 끝나는 최대합maxSoFar = 지금까지 본 전체 최대합을 유지하며 한 칸씩 전진 점화식:maxEndi..

문제[프로그래머스] 올바른 괄호사용 알고리즘- 스택 자료구조 (를 쓰지 않아도 가능) 해결방법'(' 이 나오면 스택에 데이터 인풋 (암거나 괜찮다)')' 이 나오면 스택에서 데이터 pop스택이 최종적으로 비어있다면 모든 쌍이 맞은 것으로 판단But? >> 스택을 쓰지 않고, 단순하게 int 변수 +- 로도 가능소스코드사용언어 : Java 1. stack 사용 코드class Solution { boolean solution(String s) { Deque st = new ArrayDeque(); for(char c : s.toCharArray()) { if (c == '(') st.push(1); ..

문제 [백준] 합이 0 (Olympiad > International Autumn Tournament in Informatics > 2011 > Group B (Juniors) 3번) 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 사용 알고리즘 - 이분탐색 - 투 포인터 - 정렬 해결방법 입력받은 학생들의 코딩실력 수열을 벡터 code_lv에 저장한 후 오름차순 정렬한다 N명의 학생 중 코딩실력의 합이 0이되는 3명을 고르는 문제이므로 2중 for문을 돌며 벡터에서 2명의 학생을 고른후, 나머지 한 명은 이분탐..

문제 [백준] 진우의 민트초코우유 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 사용 알고리즘 - 브루트포스 - 구현 해결방법 문제조건에서 우유의 총합이 10개를 넘지 않는 단 것이 포인트 가능한 우유 좌표의 순열을 모두 탐색해서, 민우가 집으로 돌아올 수 있다는 전제하에 마실 수 있는 최대 우유 개수를 구한다 (*순열 : 시퀀스에 담긴 원소를 중복없이 순서에 상관있게 나열하는 것) 예를 들면, 우유가 총 3개 있다고 했을 때, 각각의 우유 좌표를 벡터에 저장한다 {{1,1}, {3,4},..

문제 [백준] 트리의 기둥과 가지 (Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest > 초급 E번) 사용 알고리즘 - 깊이 우선 탐색 (DFS) 해결방법 루트노드가 주어지므로, 루트노드부터 DFS 탐색 기가노드를 만난 경우 => 기둥의 길이 도출 (gi_len) 리프노드를 만난 경우 => 가지의 길이 도출 (ga_len) 예외 케이스 루트노드가 기가노드인 경우 = 기둥 길이는 0 기가노드가 리프노드인 경우 (사실상 기가노드가 존재하지 않는 경우) = 가지 길이는 0 반례 케이스 기가노드가 루트노드인 경우, 2개의 자식을 가지는 노드 3번이 기가노드로 체크될 수 있다. 이 부분을 유의해서 풀었음 더보기 ..

문제 [백준] 파스칼 삼각형 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 파스칼의 삼각형은, x == 0 일땐 무조건 1을 가진다 dp[y][x] = dp[y-1][x-1] + dp[y-1][x] 대칭구조 이므로, 절반만 dp를 채우고, 내부 합을 구할 때 dp 값이 없는 경우, 대칭위치의 값을 사용해 연산한다 dp[3][0], dp[3][1] dp[4][0], dp[4][1] dp[5][0], dp[5][1], dp[5][2] dp[6][0], dp[6][1], dp[6][2] .... 소스코드 사용언어 : c++ #include using namespace std; int dp[31][31]; int main() { int R, C, W; cin >> R >> C >>..