본문 바로가기

전체 글

 (50)
정렬 오름차순과 내림차순 오름차순 : 1 -> 2 -> 3 -> ... (그래프를 그렸을 때 증가하는 모양) sort() 함수 사용 내림차순 : 9 -> 8 -> 7 -> ... sortDescending() 함수 사용 불변성에 따른 정렬: -ed sort() mutable한 데이터집합을 정렬할 때는 sort()를 사용한다 sorted() immutable한 데이터집합을 정렬할 때 -ed가 붙은 sorted()를 사용하면 원본 리스트는 변경하지 않고 정렬된 값을 새로운 리스트에 담아 반환한다. - immutable한 List를 정렬할 때는 : sorted() 사용 - mutable한 MutableList를 정렬할 때는 : sort(), sorted() 둘다 사용 가능 (sorted()의 경우 List로 반환)..
시뮬레이션 구현하기 까다로운 구현 문제를 시뮬레이션이라고 한다 어려운 알고리즘을 쓰는 건 아니고 풀릴 것 같은데 막상 구현하려고 하면 꽤나 복잡해서 어떻게 해야 할지 모르겠는 문제들이다 푸는 것도 푸는 건데 문제가 길고 복잡해서 읽는 것도 힘들닿; 시간이 많지 않아서 문제 풀이 시간을 1~2시간으로 정해두고 그 안에 안 풀리면 답을 봤다 지금까지 풀어본 시뮬레이션 문제 유형 유형 1. 진짜 구현 (알고리즘 안쓰고 푸는 문제: 재귀, 반복문 등등) 유형 2. bfs+ 구현 유형 3. 백트래킹 + 구현 (풀이를 찾아보면 백트래킹 하는 부분을 dfs라고들 하는 것 같다) 유형 4. bfs + 백트래킹 + 구현 구현 - 배열 회전 시키기, 배열 한 방향으로 데이터 옮기기 등등 BOJ 15683 감시 몰라도 일단 풀어보라고..
백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 조건에 맞지 않는 후보는 제외하면서 탐색하여 불필요한 재귀 호출을 줄일 수 있다 BOJ 15649. N과 M (1) 순서가 있는 숫자 조합 출력하기 arr : 출력할 숫자를 담을 배열 isUsed : 현재 사용된 숫자를 구분하기 위한 배열 (isUsed[2] = 1 : 숫자 2는 이미 조합에 사용되었다) k: 현 인덱스, 몇번째 숫자까지 채웠는지 알 수 있다 구현 base condition : k == m 그동안 arr에 모은 숫자를 출력한다 backtracking isUsed[i] == 1 : 사용된 숫자라면 제외한다 isUsed[i] == 0 : 아직 사용하지 않은 숫자일 경우 arr에 추가 arr[k] = i, 사용했다는 표시 is..
재귀 이번주 목표는 재귀 파트 넘기기 재귀 나에게 매우 어렵다 예전에도 알고리즘 공부하다가 재귀 파트에서 포기했던 기억이 난다 이젠 포기도 불가능 많이 풀어서 외워버릴테다 재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 함수를 명확하게 정의해야 함 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다 -> 반복문보다 메모리/시간에서 손해를 본다 자기 자신을 여러 번 호출하면 비효율적일 수 있다 -> 동일한 연산을 하는 함수 호출이 반복될 경우 재귀의 조건 1. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 : base condition 2. 모든 입력은 base condition으로 수렴해야 함 1,2중 한 조건이라도 무시된다면 무한으로 돌게 됨 절차지향적 사고를 탈피..
BFS 응용문제 풀기 2206. 벽 부수고 이동하기 최단거리 구하는 BFS 문제인데 벽을 하나 부술 수 있다는 조건이 추가되었다 최단 경로로 이동하기 위해 어떤 벽을 부숴야 하는지를 어떻게 구해야 할까 고민됐다 일단 모든 벽을 하나 하나 부쉈을 때 각 최단경로가 어떻게 되는지를 구하는 방법이 생각났는데 시간 초과가 나올 것 같았지만 생각나는 방법이 없어서 도전해봤더니 역시나 시간초과 변수에 벽을 부쉈는지 여부를 저장하고 이를 확인하여 벽을 부수지 않은 경우 벽을 만나면 부수는 방법도 생각해 봤으나, 0 1 (*) 0 1 (#) 1 0 1 0 0 이런 경우 # 위치의 벽을 부쉈기 때문에 이미 벽을 부쉈다는 체크가 되어있어 * 위치 벽을 부수지 못하고 탈출이 불가능하게 된다 다른 풀이를 봤더니 3차원 배열을 사용하고 있었다 (절..
BFS 기본 문제 1012. 유기농배추 배추 지렁이는 인접한 배추들을 이동하며 해충을 잡아 먹는다 밭 군데군데 배추를 심어뒀기 때문에 배추 벌레가 이동할 수 없는 공간이 존재한다 배추밭 전체를 보호하기 위해 필요한 배추 지렁이는 몇마리인가? -> BFS 기본 유형 가로 세로 바꿔 풀어서 약간 헷갈렸다 import java.io.* import java.util.* lateinit var graph: Array lateinit var visited: Array fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val t = readLine().toInt() val bw = BufferedWriter(OutputStreamWriter(System.out)..
BFS Breadth First Search 인접한 노드를 먼저 탐색하는 방법 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 최단 경로, 임의의 경로를 찾고 싶을 때 사용한다 큐를 이용하여 구현할 수 있다 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다 2. 큐에서 원소를 꺼내어 그 칸에 인접한 칸(상,하,좌,우)에 대해 3번을 진행한다 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다 4. 큐가 빌 때까지 2번을 반복한다 모든 칸이 큐에 한번씩 들어가므로 시간복잡도는 칸이 N개일 때, O(N)이고, 행이 R개 열이 C개라면 O(RC) ->bfs를 돌 때 큐에 쌓이는 순서는 거리순이다 구현 시 주의할 점 ..
스택의 활용 : 수식의 괄호쌍 수식의 괄호 쌍 주어진 괄호 문자열이 올바른지 판단하는 문제 해결방법 문자열을 앞에서부터 읽어나가며, 닫는 괄호가 나올 경우 가장 최근에 나왔던 여는 괄호와 짝을 지어본다 이때 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다 가장 나중에 입력된 괄호가 가장 먼저 나오기 때문에 스택구조를 응용하면 해결이 가능하다 여는 괄호가 나오면 스택에 저장하고 닫는 괄호를 만나면 스택 top 값과 비교한다 짝이 지어진다면 pop으로 없애고, 짝이 지어지지 않는 괄호가 있다면 바르지 않은 괄호쌍이다 BOJ 4949. 균형잡힌 세상 조건 (), [] 2종류의 괄호로 이루어진 문자열이 올바른 괄호쌍을 이루고 있는지 판단한다 해결 1. 여는 괄호가 나오면 스택에 넣는다 2. 닫는 괄호가 나오면 스택 top에 있는 값..

티스토리툴바