본문 바로가기

분류 전체보기

 (62)
13549번 - 숨바꼭질 3 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 13549번 - 숨바꼭질 3을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/13549  [문제 접근]저는 이 문제를 풀지 못했습니다. 정확히는 방향성을 잡지 못했습니다. 항상 유형별 문제만 풀다가, 유형을 모르는 문제를 풀려고 하니까 방향성을 잡기가 어렵네요.처음에는 그리디로도 생각했다가,, DP도 생각했는데, 정당성 그리고 점화식을 세울 수가 없더라구여.1시간을 고민 끝에 결국 문제 관련 자료를 찾아보았고, 그래프와 관련된 문제라는 것을 알 수 있었습니다.그래서 저는 BFS로 접근했고 풀어냈습니다!.근데 이 문제를 BFS로 풀어서 맞춘 것은 순전히 우연이었습니다. 이 문제는 우리가 알고 있는 BFS를 단순히 사용해..
[백준/C++] 알고리즘 2011번 - 암호 코드 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 2011번 - 암호 코드를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2011 [문제 접근]읽어보면 이전상황을 이용해 현재 상황을 구한다는 느낌이 옵니다.즉 패턴을 발견할 수 있습니다. 동일한 구조의 작은 문제들의 해법을 이용해 동일한 구조의 큰 문제의 해법을 구할 수 있습니다.즉 다이나믹 프로그래밍 냄새를 술술 풍깁니다. [풀이 전략]다이나믹 프로그래밍의 첫번째 단계는 점화식 정의입니다.저는 dp[i]를 i번째까지 해석가짓수로 정의하였습니다.왜냐구여? 일단 가장 문안하게 정의내렸습니다.이렇게 했는데 점화식이 안구해지면 그에 맞춰서 dp[i] 정의를 다르게 하거나 dp[i][j] 정의로 변경하면 됩니다. i번째 ..
[백준/C++] 알고리즘 9655번 - 돌 게임 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 9655번 - 돌 게임 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/9655 [문제 접근]여러가지 접근 방법이 있지만, 다이나믹 프로그래밍을 연습하는 목적으로, 다이나믹 프로그래밍 방법을 시도하였습니다.이 문제가 다이나믹 프로그래밍 냄새를 풍기는 부분이 있습니다. 바로 현재 상황 n을, n-1 이전 상황 혹은 n-3 이전 상황을 이용하여 구할 수 있기 때문입니다. 그래서 구체적으로 다음 스텝은 뭐냐구여?.점화식 정의를 해야합니다.저는 처음에 풀이를 했을 때 점화식 정의를 잘못하여 풀었는데 풀리는 이상한 상황이 발생하였습니다.  저는 dp[i]를 "i번째 돌이 남았을 때 이기는 사람"이라고 정의를 했습니다.n-1이전상..
[백준/C++] 알고리즘 10942번 - 팰린드롬? 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 10942번을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/10942 [문제 접근]시간 제한은 0.5초M의 크기는 1백만, N의 크기는 2천입니다.여기서 완전탐색으로 질문 1번에 수열을 모두 탐색을 하면 n번 연산이 필요하기 때문에 총 연산량은 M x N 으로 20억연산이 됩니다.c++에서 1초에 대략 1억번 연산을 한다고 했을 때, 20초로 시간 초과가 납니다.즉 이 문제는 O(N)의 시간복잡도를 가진 알고리즘으로 접근해야 하고, 다이나믹 프로그래밍이 적합하다는 것을 유추할 수 있습니다. O(NlogN)시간복잡도를 가진 알고리즘을 생각할 수 있지만, 팰린드롬의 반복성을 생각했을 때 다이나믹프로그래밍+ O(N)이 더..
[iOS] Combine 프레임워크 안녕하세요. 테크지니어22입니다.오늘은 combine 프레임워크에 대해서 알아보도록 하겠습니다. 1. Combine이란 ?선언적 방식으로 비동기 프로그래밍을 단순화한 반응형(Reactive) 프레임워크선언적이면 뭐가 좋아?선언형은 how가 아니라 what에 집중한 방식.데이터 흐름이 간결해지고, 체이닝을 통한 직관적 코드 작성이 가능함. → 이는 곧 유지보수를 용이하게 함.반응형이란?변화하는 데이터나 이벤트에 따라 자동으로 반응.2. Combine이 탄생한 이유기존 비동기 처리 방식의 한계콜백 지옥 발생데이터 흐름 추적 , 유지보수 어려움NotificationCenter & KVO (Key-Value Observing)의 복잡성옵저버 등록/해제 필수놓쳤을때 메모리 관리 이슈 발생 가능.클로저 기반 비동..
[백준/C++] 알고리즘 2660번 - 회장뽑기 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2660  [문제 접근]처음에 문제를 읽고 머릿속에 명확히 문제 상황이 그려지지 않았습니다.그래서 예제를 토대로 그림을 그려가며 이해를 시도했습니다. 사람을 정점으로, 친구관계를 간선으로 치환하여 생각했고,조건에서 몇 사람을 통하면 모두가 서로 알 수 있다고 했기 때문에 BFS를 이용해서 거리가 가장 먼 정점을 점수로 두었습니다.인접리스트를 활용하여 BFS를 둘 경우에는 O(V+E)의 시간복잡도가 걸립니다.제한시간은 1초이지만, 회원의 수가 50명이하여서, O(V+E) * 50 충분히 제한시간 안에  들어갈 수 있다고 판단하였습니다. [풀이 전략]1. 무방향 그래프임..
[프로그래머스 LV3/C++] 알고리즘 - 코딩테스트 공부 안녕하세요! 테크지니어22입니다. 오늘은 프로그래머스 알고리즘 - 코딩테스트 공부를 풀어보도록 하겠습니다. 문제가 어렵네요. 해설을 보았는데도 어려워서 독백체로 작성을 하면서 이해를 했습니다. https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근 ] + [풀이 전략] 최단 시간을 구하는 최적화 문제이다. 처음에 다양한 자료구조와 알고리즘이 떠올랐다. 다이나믹 프로그래밍, 백트래킹, BFS 등 이 떠올랐지만 방향성이 보이지 않았다. 그래서 ..
[프로그래머스 LV3/C++] 알고리즘 - 등산 코스 정하기 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘  등산 코스 정하기를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/118669 [문제 접근]휴식 없이 이동해야 하는 시간 중 가장 긴 시간인 intensity를 숙지하는 게 제일 중요합니다. 저는 이를 잘못이해하면 풀이를 하는데 시간을 많이 잡아먹었습니다. 여러 출입구 와 산봉우리가 있는데, 출입구에서 산봉우리까지 이동하면 intensity들을 파악하고 이 intensity들 중에서 가장 최소인 intensity를 경로 중에 가지고 있는 산봉우리의 번호를 찾아야 합니다. 이때 intensity가 같다면 산봉우리번호가 작은 것이 정답입니다. intensity의 정의..
[프로그래머스/C++] 알고리즘 - 표현 가능한 이진 트리. 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 표현 가능한 이진 트리를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근처음에는 삽질을 했습니다. 중위 순회를 파악해서 중위 순회한 트리를 원래 트리로 복원하는 방법도 고려해보았습니다.하지만 이 문제의 핵심은 루트노드, 서브 루트 노드의 값을 살펴보는 것입니다.리프노드를 제외한 서브 루트 노드들의 값이 1일 때 참입니다. 이때 루트 노드를 체크하고,..
[C++] 다이나믹 프로그래밍(Dynamic Programming) 안녕하세요! 테크지니어22입니다.오늘은 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다. 다이나믹 프로그래밍(DP)이란?- 여러 하위 문제들로 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘- 일반적으로 시간복잡도는 O(n^2) or O(n x m)형태로 나타남. 언제 자주 사용되는가? - 최적화문제(최대,최소) -> n이 커서 백트래킹이나, 완전탐색 등으로 구할 수 없는 경우 유용- 중복되는 부분 문제 어떻게 사용하는가?전체 문제를 하위 문제로 쪼개고 이를 이용하여 전체 문제로 해결가능한 지 파악하기테이블 정의하기1차원으로 최대한 정의를 해보기(관점을 달리하기 혹은 비틀어보기)어렵거나 추가 정보가 요구되면 2차원 정의 해보기점화식 찾기초기값 설정하기DP 배열 채우기탑다운 방식->재귀 사용바텀..

티스토리툴바