티스토리

민규의 흔적

검색하기

블로그 홈

민규의 흔적

ymg5218.tistory.com/m

공부한 흔적

구독자: 7

방명록 방문하기

주요 글 목록

[알고리즘] 위상 정렬(Topological Sort) [ 백준 2252번 - 줄 세우기 ] 2024년 11월 26일위상 정렬 위상 정렬이란, 순환하지 않는 유향 그래프(DAG, Directed Acyclic Graph)를 방향성에 거스르지 않도록 순서대로 배열하는 방법이다. 이게 무슨 의미인가. 다음 예시를 통해 쉽게 이해해보자. 나는 어떤 RPG 게임을 시작하려고 한다.해당 RPG 게임에서는 첫 레이드인 A 보스 레이드에 참여하기 위해서 50레벨을 달성하고 모든 장비 강화를 10단계 이상 달성해야 한다.그리고 다음 레이드인 B 보스 레이드에 참여하기 위해서, A 보스 레이드를 클리어한 상태에서 모든 장비 강화를 15단계 이상 달성해야 한다.그리고 장비를 업그레이드 하기 위해서는 B 보스 레이드를 클리어한 상태에서 기존 장비를 상위 장비로 계승해야 한다. 어떤 RPG 게임에서 내가 이룩하고 싶.. 공감수 2 댓글수 0 2024. 11. 26.
[알고리즘] 패턴 매칭 알고리즘, KMP 알고리즘 ( Knuth–Morris–Pratt Algorithm ) 오탈자나 오류를 범한 내용이 있다면 댓글 남겨주세요!! 언제든 환영합니다!!!!!2024년 10월 10일 패턴 매칭 당장 ctrl + F를 누르면 현재 페이지에서 찾고자 하는 키워드를 손쉽게 찾을 수 있는 기능이 존재한다.이와 같이 전체 문자열에서 특정 키워드(패턴)을 찾는 것을 패턴 매칭이라고 부른다. 패턴 매칭 알고리즘 문자열 패턴 매칭 알고리즘은 워드패드, 논문, 웹 페이지 등에서 원하는 키워드를 검색할 때 빠른 속도로 찾게 해주는 중요한 역할을 한다.문서 전체의 길이가 길수록, 그리고 검색하려는 키워드(패턴)의 길이가 길수록 효율적인 패턴 매칭 알고리즘을 필요로 하게 된다. 패턴 매칭 알고리즘에는 여러 가지가 존재하지만, 이 글에선 브루트포스( brute force ) 방식과 KMP 알고리즘 방식.. 공감수 6 댓글수 6 2024. 10. 10.
[Python 파이썬] 백준 2583번 - 영역 구하기 2024년 10월 2일문제 링크 : 백준 2583번 - 영역 구하기 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램.. 공감수 0 댓글수 0 2024. 10. 2.
[Python 파이썬] 백준 1926번 - 그림 2024년 10월 2일문제 링크 : 백준 1926번 - 그림 문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.입력첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)출력첫째 줄에는 그림의 개수, 둘째 줄에는 그.. 공감수 0 댓글수 0 2024. 10. 2.
[Python 파이썬] 백준 5972번 - 택배 배송 2024년 9월 26일문제 링크 : 백준 5972번 - 택배 배송 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-.. 공감수 2 댓글수 1 2024. 9. 26.
[Python 파이썬] 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 2024년 9월 24일문제 링크 : 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 문제 접근 현재 나의 숙련도에 따라 퍼즐을 푸는 시간이 달라진다. diffs의 각 요소는 최대 100000이므로, 나의 숙련도는 1 ~ 100,001일 것이다. 1 부터 100,001 까지 일일이 확인해보기엔 시간복잡도 측면에서 좋을 게 없다. (퍼즐의 개수 n의 최대 값은 300,000 이므로, 최악의 경우 100,001 * 300,000 ~= 10^10번 연산해야 한다.) 그러므로 우리는 효율적으로 숙련도의 최소값을 찾아야 한다. 어떻게? 이분 탐색으로! 내가 가질 수 있는 숙련도의 범위는 1 ~ 100,001 이므로 양 끝 값인 left, right는 각각 1, 100,001로 초기화 시켜준다. le.. 공감수 4 댓글수 2 2024. 9. 24.
[Python 파이썬] 프로그래머스 - 과제 진행하기 2024년 9월 24일문제 링크 : 프로그래머스 - 과제 진행하기 문제 접근 주어진 데이터를 자신이 원하는 목적에 맞게 가공하여 활용할 수 있는지가 문제의 난이도를 좌우한다고 생각한다. 구현 문제는 문제에서 요구하는 바를 정확히 이해해야 한다. 1. plans의 요소들은 진행할 과제들에 대한 정보를 담고 있으며, 이는 [과제명, 과제 시작시간, 소요시간]으로 이루어져 있다. 2. 과제는 시작하기로 한 시각이 되면 시작한다. 3. 새로운 과제를 시작할 시간이 되었을 때, 기존에 진행하고 있던 과제가 있다면 해당 진행을 멈추고 새로운 과제를 시작한다. 4. 진행 중이던 과제를 끝냈을 때, 멈춰두었던 과제가 존재한다면 해당 과제를 이어서 진행한다. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시.. 공감수 0 댓글수 0 2024. 9. 24.
[Python 파이썬] 프로그래머스 - 땅따먹기 2024년 9월 10일문제 링크 : 프로그래머스 - 땅따먹기문제 접근 0번째 행부터 마지막 행까지 규칙에 맞춰 칸을 한 칸 씩 밟아가며, 최대로 많이 누적시킬 수 있는 점수를 출력하는 문제이다. 여기서 말한 규칙은 다음과 같다. 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 만약 1번째 열의 칸을 밟았다면, 다음 행에선 1번째 열 칸은 밟지 못한다는 의미이다. 마지막 행까지 도달하는 모든 경우의 수를 계산하기엔 최대 행의 개수가 100,000개로 시간복잡도가 엄청 불어나게 된다. 이를 효율적으로 풀기 위해 다이나믹 프로그래밍 기법을 활용하기로 결정하였다. DP(다이나믹 프로그래밍) 기법을 활용하고자 결정한 이유는 다음과 같다. 특정 칸 까지 누적할 수 있.. 공감수 5 댓글수 1 2024. 9. 10.
[Python 파이썬] 백준 1283번 - 단축키 지정 2024년 9월 5일문제 링크 : 백준 1283번 - 단축키 지정문제한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문.. 공감수 3 댓글수 1 2024. 9. 5.
[Python 파이썬] 백준 9095번 - 1, 2, 3 더하기 2024년 8월 14일문제 링크 : 백준 9095번 - 1, 2, 3 더하기문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 알고리즘 분류다이나믹 프로그래밍 문제 접근 테스트 케이스마다 11 미만의 양의 정수 n이 주어졌을 때, n을 1, 2, 3.. 공감수 0 댓글수 0 2024. 8. 15.
[Python 파이썬] 백준 15558번 - 점프 게임 2024년 8월 14일문제 링크 : 백준 15558번 - 점프 게임문제 상근이는 위 그림과 같은 지도에서 진행하는 게임을 만들었다.지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. .. 공감수 0 댓글수 0 2024. 8. 14.
[Python 파이썬] 백준 25195번 - Yes or yes 2024년 8월 14일문제 링크 : 백준 25195번 - Yes or yes 문제 N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 ".. 공감수 0 댓글수 0 2024. 8. 14.
[Python 파이썬] 백준 17129번 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 2024년 8월 14일문제 링크 : 백준 17129번 - 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유문제 윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있.. 공감수 0 댓글수 0 2024. 8. 14.
[Python 파이썬] 백준 4963번 - 섬의 개수 2024년 8월 9일문제 링크 : 백준 4963번 - 섬의 개수문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.입력의 마지막 줄에는 0이 두 개 주어진다... 공감수 0 댓글수 0 2024. 8. 9.
[Python 파이썬] 백준 6198번 - 옥상 정원 꾸미기 2024년 8월 9일문제 링크 : 백준 6198번 - 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다.빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = .. 공감수 0 댓글수 0 2024. 8. 9.
[Python 파이썬] 백준 18126번 - 너구리 구구 2024년 8월 6일문제 링크 : 백준 18126번 - 너구리 구구 문제 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구와 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.입력첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.다음 N-1개의 줄에 구구의 집의 모든 길의.. 공감수 0 댓글수 0 2024. 8. 7.
[Python 파이썬] 백준 1325번 - 효율적인 해킹 2024년 8월 6일문제 링크 : 백준 1325번 - 효율적인 해킹 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.입력첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 .. 공감수 0 댓글수 0 2024. 8. 6.
[Python 파이썬] 프로그래머스 - 귤 고르기 2024년 8월 6일문제 링크 : 프로그래머스 - 귤 고르기문제 접근 그리디하게 접근해 간단하게 풀 수 있는 문제라고 판단했다. 각 귤마다 이산 값을 가지며, 상자 하나에 k개의 귤을 담고자 할 때 귤의 크기 종류가 최소가 되도록 하고 싶으므로각 크기 별 귤의 개수를 딕셔너리에 저장해 각 value 값을 리스트 형태로 뽑아와 내림차순 정렬하여 종류가 많은 귤부터 상자에 넣으면 된다고 결론냈다. k = 6, tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 인 입력 예시를 들어보자. 각 크기별 개수를 딕셔너리 형태로 담아내면 다음과 같다. dict = {1 : 1, 2 : 2, 3 : 2, 4 : 1, 5 : 2} 각 value 값을 리스트 형태로 뽑아내면 다음과 같다. [1, 2, 2.. 공감수 0 댓글수 0 2024. 8. 6.
[Python 파이썬] 프로그래머스 - 네트워크 2024년 8월 6일문제 링크 : 프로그래머스 - 네트워크문제 접근 문제 자체는 엄청 간단하다. 서로 이어져있는 여러 대의 컴퓨터가 존재할 때, 각 컴퓨터끼리 이루는 네트워크의 총 개수를 구하면 되는 문제이다. 모든 컴퓨터를 하나씩 시작점으로 지정해보며 만약 아직까지 어느 네트워크에도 소속되지 않은 컴퓨터라면, 해당 컴퓨터를 시작점으로 BFS 로직을 수행해 같은 네트워크에 존재하는 모든 컴퓨터를 알아내기를 반복하면 된다. BFS 로직을 수행한 횟수가 곧 총 네트워크의 개수가 된다. 전체 코드 from collections import dequedef solution(n, computers): answer = 0 visited = [False] * n for start_v in range(.. 공감수 0 댓글수 0 2024. 8. 6.
[Python 파이썬] 백준 2841번 - 외계인의 기타 연주 2024년 7월 31일문제 링크 : 백준 2841번 - 외계인의 기타 연주문제상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 .. 공감수 0 댓글수 0 2024. 7. 31.
[Python 파이썬] 백준 2512번 - 예산 2024년 7월 19일문제 링크 : 백준 2512번 - 예산문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을.. 공감수 0 댓글수 0 2024. 7. 19.
[Python 파이썬] 프로그래머스 - 베스트앨범 2024년 7월 17일문제 링크 : 프로그래머스 - 베스트앨범 ※ 만약 2번, 15번 테스트케이스가 틀리셔서 찾아오셨다면, 다음 테스트케이스를 돌려보시기 바랍니다. genres = ["classic", "pop", "classic", "classic", "pop"]plays = [100, 500, 100, 100, 500] 문제 접근 문제에서 명시되어있듯, 핵심은 다음과 같다. 1. 각 장르마다 최대 2개의 노래를 앨범에 수록할 것이다.2. 속한 노래가 많이 재생된 장르를 먼저 수록할 것이며, 각 장르에서 가장 많이 재생된 노래를 먼저 수록할 것이다. 만약 같은 장르 내에서 재생 수가 같은 노래가 존재한다면 고유 번호가 낮은 노래를 먼저 수록한다.3. 모든 장르는 재생된 횟수가 다르다. 특히, 3번 덕.. 공감수 0 댓글수 0 2024. 7. 17.
[Python 파이썬] 프로그래머스 - 다리를 지나는 트럭 2024년 7월 17일문제 링크 : 프로그래머스 - 다리를 지나는 트럭 문제 접근 문제의 핵심은 다음과 같다. 1. 다리 위에 있는 트럭이 다리를 건널 수 있으면 건너게 하고, 이후에 다리에 트럭이 올라올 수 있으면 다리 위로 트럭을 올림2. 다리를 건널 때, 트럭은 1초에 1만큼 이동한다고 가정하며, 다리의 길이가 n이라면 n초 후에 다리를 건너게 됨3. 다리가 버틸 수 있는 한계무게가 존재하며, 한계무게를 넘어서는 트럭은 기다려야 함 특히, 1번의 경우가 중요하다고 생각한다. 문제 예시를 보면, 다리 위에 트럭이 오르고 1초마다 1씩 움직여 최종적으로 트럭이 다리를 건널 수 있다면 다리를 건너게 한 이후에 다리에 트럭을 올릴 수 있는지 확인해야 한다. 문제에서 제시된 예시는 다음과 같다. 이 과정.. 공감수 0 댓글수 0 2024. 7. 17.
[스터디 커뮤니티 홍보] 국모다 - 국비 부트캠프의 모든 것이다! 안녕하세요! 현재 저도 소속되어 있고, 저처럼 누군가와 스터디를 꾸리거나 모여서 공부하는 것을 좋아하시는 분들을 위해 홍보 게시글을 포스팅하게 되었습니다. 현재 애용하는 스터디 커뮤니티인 국모다 입니다.( 국모다 홍보 페이지 => 클릭!! ) 국모다 란? 국모다는 국비 부트캠프의 모든 것이다! 의 줄임말로,좁게는 말 그대로 국비 부트캠프에 대한 정보들이나 이를 준비하는 분들이 모여 스터디를 진행하고 있으며넓게는 IT와 관련된 스터디를 희망하는 분들끼리 모여 스터디를 진행하거나, 각자 ZEP 커뮤니티에 모여 자율적으로 공부하고 있는 활동을 진행중입니다. 대부분의 활동은 비대면으로, 가상공간인 ZEP에서 진행합니다! 주요 활동 현재 진행되고 있는 주요 활동들로는 다음과 같습니다!모각스/모각코(각자 모여서 .. 공감수 2 댓글수 0 2024. 7. 16.
[Python 파이썬] 백준 10971번 - 외판원 순회 2 2024년 7월 15일문제 링크 : 백준 10971번 - 외판원 순회 2문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 .. 공감수 0 댓글수 2 2024. 7. 15.
[Python 파이썬] 프로그래머스 - 이중우선순위큐 2024년 7월 15일문제 링크 : 프로그래머스 - 이중우선순위큐문제 접근 최소 힙과 최대 힙을 다룰 수 있는지를 묻는 문제이다. 문제만 읽어보면 최소 힙과 최대 힙 성질을 모두 갖는 하나의 자료구조를 만드는 것을 요구하지만, 실제로는 최소 힙과 최대 힙 두 가지 자료구조를 모두 활용하여 하나의 자료구조처럼 사용해야하는 문제이다. (힙 자료구조와 우선순위 큐란? : https://ymg5218.tistory.com/120) 최소 힙, 최대 힙을 모두 선언하고 값을 삽입하는 연산이 들어올 때마다 해당 값을 최소 힙, 최대 힙에 모두 삽입한다.여기서, 라이브러리가 최소 힙만 지원해준다고 최대 힙을 따로 구현할 필요는 없다. 삽입하는 값에 -1을 곱해주어 최소 힙에 저장하면, 해당 값을 꺼낼 때마다 다시 -1.. 공감수 0 댓글수 1 2024. 7. 15.
[Python 파이썬] 백준 14888번 - 연산자 끼워넣기 2024년 7월 15일문제 링크 : 백준 14888번 - 연산자 끼워넣기문제N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.1+2+3-4×5÷61÷2+3+4-5×61+2.. 공감수 0 댓글수 2 2024. 7. 15.
[Python 파이썬] 백준 3085번 - 사탕 게임 2024년 7월 12일문제 링크 :백준 3085번 - 사탕 게임문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, .. 공감수 0 댓글수 0 2024. 7. 12.
[Python 파이썬] 백준 1182번 - 부분수열의 합 2024년 7월 12일문제 링크 : 백준 1182번 - 부분수열의 합문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 알고리즘 분류백트래킹브루트포스 알고리즘 문제 접근 백트래킹을 활용해 완전탐색 해야하는 문제이다. 길이가 1일 때의 부분 수열부터 길이가 N일 때의 부분수열까지 모든 조합을 구해 합이 0이 되는 .. 공감수 0 댓글수 0 2024. 7. 12.
[Python 파이썬] 백준 14889번 - 스타트와 링크 2024년 7월 10일문제 링크 : 백준 14889번 - 스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sj.. 공감수 0 댓글수 0 2024. 7. 10.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.