난이도 D4.스택과 큐 파트에 있던 문제인데 스택도 큐를 안쓰고 풀었다. 사다리타기라 시뮬레이션만 하면 되는데, 어느 쪽에서 시작할지가 이 문제의 핵심 포인트였다. [문제]100 x 100 배열에 사다리가 그려져 있다. 세로 막대는 1이 세로로 이어진 것이고, 가로선도 1로 그려져 있다. 나머지는 0이다. 바닥 어딘가에 2로 표시된 도착점이 있다.사다리를 타는 규칙은 아는 그대로다. 아래로 내려가다가 좌우에 가로선이 나타나면 그쪽으로 꺾고, 옆 막대로 옮긴 뒤에는 다시 아래로만 간다. 바닥에 닿으면 끝이다.2에 도착하려면 맨 윗줄 어느 x에서 출발해야 하는지를 구하면 된다. 테스트 케이스는 10개 고정이고, 한 막대에서 출발한 가로선이 다른 막대를 가로질러 이어지는 경우는 없다.[내 풀이]처음엔 그냥 0..

스택과 큐 파트에 있던 문제.괄호 문자열 하나 받아서 세기만 하면 되는 거라 만만해 보였는데, 처음 짠 게 시간 초과가 나서 다시 짰다.[문제]쇠막대기 여러 개를 겹쳐 놓고 레이저로 자른다.막대기는 자기보다 긴 막대기 위에만, 완전히 포함되게 놓이고 끝점은 안 겹친다. 이 배치를 괄호로 적는다.막대기의 왼쪽 끝은 (, 오른쪽 끝은 )인접한 () 는 무조건 레이저다레이저는 어떤 막대기의 끝점과도 안 겹친다잘린 조각의 총 개수를 구하면 된다. 괄호는 최대 100,000개.입력 출력2()(((()())(())()))(()) #1 17(((()(()()))(())()))(()()) #2 24[내 ..

앞 글에서 스택과 큐를 만들었다. 그런데 스택과 큐 자체가 목적인 문제는 많지 않다. 그것들은 비선형 자료구조를 훑기 위한 도구였고, 이 글이 그 대상을 다룬다. 트리와 그래프는 "원소들 사이의 관계"를 표현한다. 리스트가 1:1 관계라면 트리는 1:N, 그래프는 N:M이다. 관계가 복잡해질수록 어떻게 저장할 것인가가 성능을 결정하고, 그래서 이 글의 절반은 표현 방식 이야기다. 마지막엔 이진 탐색 트리(BST)를 다룬다. 트리 — 정의부터 재귀적이다성질비선형 구조원소들 간에 1:N 관계를 가지는 자료구조원소들 간에 계층 관계를 가지는 계층형 자료구조정의한 개 이상의 노드로 이루어진 유한 집합이며 다음을 만족한다.노드 중 최상위 노드를 루트(root) 라 한다나머지 노드들은 n개(n ≥ 0)의 분리 집합..

배열은 아무 자리에나 넣고 뺄 수 있다. 그게 장점 같지만, 알고리즘 문제를 풀다 보면 일부러 그 자유를 버리는 자료구조를 계속 만나게 된다. 스택은 한쪽 끝에서만 넣고 빼고, 큐는 넣는 곳과 빼는 곳을 반대로 갈라놓는다. 스택은 "가장 최근 것"을 늘 알고 있고, 큐는 "가장 오래된 것"을 늘 알고 있다. 이 글은 스택 → 큐 → 원형 큐 → 연결 리스트 순으로 간다. 제한의 방향이 자료구조를 가른다스택과 큐의 차이는 딱 하나다. 넣는 곳과 빼는 곳이 같은가, 반대인가. 스택큐삽입한쪽 끝(top)뒤(rear)삭제같은 쪽 끝(top)반대쪽 끝(front)순서후입선출 LIFO선입선출 FIFO공짜로 아는 것가장 최근 원소가장 오래된 원소대표 응용괄호 검사, 함수 호출, 후위 계산, DFS버퍼, 대기 행렬,..

순열과 조합은 고등학교 확률과 통계에서 이미 배운 내용이다. 그런데 알고리즘에서 다시 배우는 이유는 개수를 세기 위해서가 아니라 실제로 만들어 내기 위해서다."경우의 수는 몇 가지인가"와 "그 경우들을 하나씩 만들어 확인하라"는 완전히 다른 요구다. 앞의 것은 공식 한 줄이면 되지만 뒤의 것은 코드가 필요하고, 그 코드가 언제까지 버티는지도 알아야 한다.이 글은 순열·조합·중복 순열·중복 조합 네 가지가 재귀에 넘기는 슬라이스 한 줄 차이로 전부 나온다는 것을 보이고, itertools 와 비트마스크까지 정리한다. 앞 글 재귀와 완전 탐색 에서 다룬 부분집합 재귀 트리를 알고 있으면 훨씬 잘 읽힌다.같은 데이터, 세 가지 질문학습 자료는 도시 여섯 개가 서로 다 연결된 그래프 하나를 놓고 질문만 세 번 ..

반복문으로 풀 수 있는 문제를 굳이 재귀로 푸는 이유가 뭘까. 코드가 짧아져서? 그것만이라면 배울 이유가 크지 않다.진짜 이유는 어떤 문제는 "더 작은 같은 문제"의 답을 알면 즉시 풀린다는 데 있다. 하노이의 탑에서 원판 20개를 옮기는 절차를 반복문으로 적으려면 머리를 싸매야 하지만, "19개를 옮길 줄 안다고 치자"고 가정하는 순간 세 줄로 끝난다. 이 글은 그 구조를 팩토리얼·피보나치·부분집합·하노이의 탑으로 확인하고, 이어서 재귀의 쌍둥이인 완전 탐색이 언제 쓸 만하고 언제 못 쓰는지를 숫자로 잡는다.반복과 재귀는 방향이 반대다반복과 재귀는 같은 답을 낼 수 있다. 다른 것은 일하는 방향이다.반복 — 작은 것부터 쌓아 올린다. sum += 1, sum += 2, … 누적값이 자란다.재귀 — 큰 ..

문제를 다 읽고 나서 가장 먼저 해야 할 일은 코드를 치는 게 아니다. 제한 조건에 적힌 N의 최댓값을 보는 것이다. N이 1,000이면 이중 반복문을 마음 놓고 써도 되고, N이 100,000이면 이중 반복문은 그 자리에서 탈락이다. 이 판단을 코드 작성 전에 못 하면, 논리가 완벽한 풀이를 다 짜고 나서 시간 초과를 받고 처음부터 다시 시작하게 된다.이 글은 그 판단을 하기 위한 기준선 하나를 만드는 정리다. "1억 번 연산 ≈ 1초" 라는 숫자 하나만 손에 쥐면, 제한 시간과 입력 크기에서 허용 복잡도를 역산할 수 있다. 앞쪽 절반은 그 기준선을 세우는 데 쓰고, 뒤쪽 절반은 그 감각을 2차원 리스트 순회와 델타 탐색이라는 실제 코드로 잇는 데 쓴다. 격자 문제에서 삼중 반복문이 나왔을 때 "이게 ..

파이썬을 배운 지 얼마 안 됐더라도, 이런 코드는 이미 수십 번 썼을 것이다.'hello'.upper()[3, 1, 2].sort(){'a': 1}.keys()문자열 뒤에 점을 찍고 함수 같은 걸 부른다. 리스트도 딕셔너리도 똑같이 동작한다. 그런데 왜 upper(문자열) 이 아니라 문자열.upper() 인가? 그냥 파이썬 문법이 그런 것이라고 넘기기 쉽지만, 사실 이 점 하나에 클래스와 객체지향이 통째로 들어 있다.'hello'.upper() 는 파이썬 내부에서 str.upper('hello') 로 동작한다. str 이라는 클래스가 있고, upper 는 그 클래스의 함수이며, 'hello' 는 그 함수의 첫 번째 인자로 들어간다. 우리가 self 라고 부르는 그 자리다.이 글은 그 한 줄에서 출발해 클..