본문 바로가기

IT 공부104

짝 찾기 문제와 스택의 본질 1. 짝 찾기 문제 문제는 아래와 같다. ( 또는 ) 로만 구성된 문자열 s가 주어진다. 문자열 s가 올바른 괄호이면 true를 return하고, 올바르지 않다면 false를 return 하는 solution 함수를 작성하라. 괄호가 바르게 짝 지어졌다는 것은 ( 문자로 열렸다면 반드시 ) 문자로 닫혀야 한다는 뜻이다. 예를 들어, "()()" 는 올바른 문자열이다. "(())()" 도 올바른 문자열이다. 문제의 해답은 스택을 사용하면 아주 쉽게 풀린다. 아이디어도 매우 간단하다. 문자열을 순서대로 접근해 스택에 넣는다. 이때 닫는 괄호 )가 나오면 스택에서 데이터를 하나 pop 하자. 해당 문자 ( 는 이제 처리되어 소거된다. 이런 논리를 계속 반복하다보면 문자열 접근이 완료되면 스택도 전부 비어있게 .. 2023. 11. 10.
처음부터 문제를 잘못 접근했다면 (feat. 그래프 알고리즘) 1. 방의 개수 찾기 문제 원점 (0, 0)에서 시작해서 위와 같이 숫자가 적힌 방향으로 이동하며 선을 긋는다. 그림을 그릴 때, 사방이 막히면 방 하나로 센다. 이동하는 방향이 담긴 배열이 매개변수로 주어질 때, 방의 개수를 반환하도록 solution 함수를 작성하세요. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 먼저 해답에 대해서.. 이 문제의 해답에 대한 큰 아이디어는 다음과 같다. 각 점을 그래프의 노드라고 하고, 연결하는 선을 간선이라고 하면 이 문제의 자료구조는 그래프가 된다. 하나의 방은 (0,0)에서 시작해 이미 방문했던 노드로 다.. 2023. 11. 9.
개발자의 문제 해결 역량이란? (feat. 구글 면접 시뮬레이션) 글로벌 소프트웨어를 말하다, 지혜 『글로벌 소프트웨어를 말하다, 지혜』는 소프트웨어에 대한 근본적인 이해와 통찰력인 지혜를 통해 글로벌 소프트웨어로 나아갈 수 있도록 안내한 책이다. 소프트웨어를 꿈꾸는 대학생들과 취업준비생, 소프트웨어 개발자, 글로벌 소프트웨어를 만들고 싶어하는 회사의 CEO, CTO, 경영진 등에게 글로벌 소프트웨어를 개발하는 데 필요한 ‘지혜’가 무엇인지 일깨워준다. 이 책은 이야기 형식으로 구성되어 있어 쉽고 재미있게 읽을 수 있고, 실리콘밸리의 소프트웨어 회사와 국내 소프트웨어 회사의 차이점과 그 이유를 짚어주며, 오래도록 개발자로 살아남을 수 있는 길을 제시한다. 저자 김익환 출판 한빛미디어 출판일 2014.06.05 라는 책에서 구글의 면접 시뮬레이션에 대해 저자가 상상한 간.. 2023. 11. 8.
오늘의 피드백 - 거꾸로 생각할 때 주의할 점. 1. N개의 수열에서 구간의 합이 최대인 구간 찾기 문제는 아래와 같다. N개의 정수가 담긴 수열이 주어진다. 이때 특정 구간의 합이 최대가 되는 구간을 찾는 효율적인 방법은? 문제는 워낙 간단하다. 그래서 무식하게 풀 수 있다. 존재할 수 있는 모든 구간 (p, q) 범위를 for 문을 통해 일일이 접근한다. 해당 구간의 합을 구해서 최대인지 확인한다. 그러나 이러한 방식은 시간복잡도가 사실상 쓸모 없는 수준이다. O(N^3)이다. 무려 세제곱이다. for 문을 통해 모든 p, q 구간을 접근해야 하므로 N 제곱의 처리가 소요되고, 또 더하기 연산을 위해서 또 O(N)이 필요하다. 즉, 복잡도는 세제곱이다. 개선해봤자 O(N^2)이 될 뿐이다. 특정 p 값에서 시작해서 q를 하나씩 늘려나가면 이전에 사.. 2023. 11. 7.

티스토리툴바