본문 바로가기
반응형

전체 글24

[프로그래머스 LV2] 요격시스템 정말 오랜만에 포스팅합니다. 그동안 일하느라 바쁘기도 했고, 알고리즘 공부도, CS 공부도 조금 소홀하긴 했습니다. 아무튼 오늘 풀어본 문제는 프로그래머스의 요격시스템이라는 문제입니다. 이 문제는 파이썬으로 해결하였습니다. 참고로 코드만 올려놓으면 가끔씩 제가 푼 문제를 제가 봐도 이해가 안 되는 경우가 있어서, 쉽게 설명을 해볼까 합니다. 참고로 해당 문제는 문제 바로가기 링크를 눌러서 확인하실 수 있습니다. 문제 설명 위 사진은 해설을 쉽게 이해하기 위해서 캡쳐해온 문제 설명입니다. 자세한 내용은 프로그래머스 홈페이지에서 확인해 보시기 바랍니다. 아래 사진은 제한사항과 입출력 예입니다. 문제 해결 아이디어 링크에서 입출력 예에 있는 사진을 보고 아이디어를 얻었습니다. 입출력 예 설명의 사진을 보면 1.. 2023. 4. 29.
[최대공약수 알고리즘] 유클리드 호제법 최대공약수를 구하는 알고리즘은 다양하겠지만 오늘은 유클리드 호제법에 대해서 알아보고자 합니다. 호제법이라는 말은 두 수가 서로 상대방 수를 나누어 결국에는 원하는 수를 얻어내는 알고리즘입니다. 유클리드 호제법 유클리드 호제법은 두 자연수 A와 B의 최대공약수를 구하는 알고리즘입니다. 이때, A가 B보다 크다고 가정합시다. 그렇다면, A를 B로 나누었을 때 나머지가 R이라고 하면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 동일합니다. 말로만 설명하면 무슨 말인지 모르겠으니, 예시를 들어보도록 하겠습니다. 예를 들어서, A와 B를 각각 192과 168이라는 자연수로 설정해봅시다. 192를 168로 나누었을 때의 나머지는 24입니다. 따라서 168과 24의 최대공약수를 구하면 됩니다. 24는 168의.. 2022. 11. 6.
서블릿(Servlet) 컨테이너에 대해서 일반적으로 웹 서버는 정적인 페이지만 제공합니다. 그렇기에 동적인 페이지를 제공하기 위해서는 웹 서버는 다른 곳에 요청하여 동적인 페이지를 작성해야 합니다. 여기서 웹 서버가 동적인 페이지를 제공할 수 있도록 도와주는 애플리케이션이 서블릿(Servlet)입니다. 즉, 서블릿은 클라이언트가 어떤 요청을 하면 그에 대한 결과를 다시 전송해주는 역할을 합니다. 서블릿 특징 서블릿은 클라이언트의 요청에 의해 동적으로 작동하는 웹 애플리케이션 컴포넌트이며, HTML을 사용하여 요청에 응답합니다. 이 때 자바의 스레드를 이용하여 동작하고, MVC 패턴에서 컨트롤러로 이용됩니다. 그리고 HTTP 프로토콜 서비스를 지원하는 javax.servlet.http.HttpServlet을 상속 받습니다. UDP보다 처리 속도가.. 2022. 10. 30.
너비우선탐색 BFS와 깊이우선탐색 DFS 너비우선탐색(BFS) 너비우선탐색(BFS)은 시작 노드에서 너비를 우선으로 탐색한다. 깊게보다는 넓게 탐색하는 방법이다. 너비우선탐색은 주로 queue 자료구조를 이용해서 구현한다. 탐색 시작 노드를 큐에 삽입하고 방문 처리 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모드 큐에 삽입하고 방문 처리 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 from collections import deque def BFS(graph, start, visited): #큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) visited[start] = True #현재 노드를 방문처리 while queue: #큐가 빌때까지 반복 v=queue.pople.. 2022. 10. 13.
계수정렬과 퀵정렬 계수정렬 계수정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다. 또한, 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다. 계수정렬의 시간복잡도는 O(N+K), 공간복잡도도 O(N+K)입니다. 계수정렬의 파이썬 코드 #모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] #모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화) count = [0] *(max(array)+1) for i in range(len(array)): count[array[i]] += 1# 각 데이터에 해당하는 인덱스의 값 증가 for i in range(.. 2022. 10. 12.
[이코테 - DFS/BFS] 미로탈출 미로탈출 문제는 BFS를 이용해서 풀었습니다. 역시 DFS와 BFS부터 문제의 난이도가 높아지는 것 같습니다. 아직 안익숙해서 그런거일지도.. 아무튼 미로탈출 문제에 대해서 설명을 시작하도록 하겠습니다. 문제 설명 N x M 크기의 직사각형 형태의 미로가 주어졌을 때 거치는 탈출하기 위한 최소 칸의 수를 구하시오. 첫 칸은 무조건 (1, 1)이고 탈출 칸은 (N, M)이다. 입력조건은 첫째 줄에 두 정수 N, M이 주어지고(4 = 0 and nc = n or ny = m: continue # 벽인 경우 무시 if graph[nx][ny] == 0: continue # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 if graph[nx][ny] == 1: graph[nx][ny] .. 2022. 10. 11.
[이코테 - DFS/BFS] 음료수 얼려먹기 dfs 문제를 상당히 오랜만에 풀어보기 때문에 익숙해질 때까지 시간이 걸릴 것 같다는 생각이 든 문제였습니다. 그래도 옛날엔 어느정도 문제를 많이 풀었었는데, 최근에는 거의 다 까먹은 것 같습니다. 각설하고 이제 바로 문제를 보도록 하겠습니다. 문제 설명 N x M 크기의 얼음틀이 있는데, 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상하좌우로 연결되어있고, 얼음틀이 주어졌을 때 만들 수 있는 아이스크림의 개수를 구하는 문제입니다. 물론, 연결된 부분에서 나오는 아이스크림은 1개로 취급합니다. 입력조건은 첫째줄에 N과 M이 주어지고, 둘째줄부터 얼음틀이 주어집니다. 이 때, 0은 뚫려있는 부분이고 1은 막혀있는 부분입니다. 출력 조건은 한 번에 만들 수 .. 2022. 10. 10.
[이코테 - 구현] 게임 개발 이번 문제는 생각보다 다른 문제들보다 길고 어려웠습니다. 열심히 짱구를 굴려가며 코딩해봤지만 계속 틀렸습니다.. 그래도 계속 보다 보니까 어느정도 이해가 돼서 꽤 잘 풀었던 것 같습니다. 문제 설명 1. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3. 만약 네 방향이 모두 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이 때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘.. 2022. 10. 9.
반응형

티스토리툴바