전체 글315 [백준 1495] 기타리스트 (Swift) https://www.acmicpc.net/problem/1495 DPN개의 곡마다 볼륨을 조정할 수 있는 크기가 주어진다. 무조건 그 곡을 연주할 때는 현재 볼륨에서 V[i] 를 빼거나 더한 볼륨으로 연주해야함시작 볼륨이 주어지고 볼륨의 최대치가 주어질 때, 마지막 곡을 연주할 수 있는 가능한 최대 볼륨을 출력하는 문제 접근방법이게 DP인지 완탐인지 모르게 풀이하긴 했다.처음에는 2차원 배열에 볼륨을 올리는 경우와 내리는 경우를 저장해서, 최대값을 갱신하는 식으로 하려고 했는데, 뭔가 고려하지 못하는 경우의 수가 있을 것 같았다..저번에 퇴사 문제 풀 때도 이렇게 풀어서 틀렸던 기억그래서 일직선에 0부터 M까지의 볼륨이 나타나있다고 가정하고, 시작 볼륨을 출발지라고 생각하면서출발지로부터 볼륨을 더하고 .. 2025. 3. 11. [컴퓨터구조] 상호배제(Mutual Exclusion) 뮤텍스(Mutex) & 세마포어 (Semaphore) 동일한 데이터를 동시성 프로그래밍 등으로 인해 여러 프로세스, 여러 스레드가 동시에 접근할 수 있다면, 다른 프로세스에 의해서 변경되거나 삭제된 값으로 인해 다른 프로세스에서 오류가 발생할 수 있다.여러 프로세스가 동시에 접근하는 데이터 영역을 임계 영역(Critical Section)이라고 부르고 이를 최소화할 수 있도록 프로그램을 설계하는 것이 중요하다.동일한 데이터를 여러 프로세스가 동시에 접근해서 사용한다면 오류가 발생할 수 있기 때문에, 한 프로세스가 해당 자원을 사용하고 있을 때 다른 프로세스의 접근을 막는 상호배제(Mutual Exclusion) 방법이 필요하다. 이 상호 배제 방법에는 세마포어와 뮤텍스가 있다. 두 방법 모두 자원에 대해서 mutex, semaphore에 관한 명령어를 호출.. 2025. 3. 10. [컴퓨터구조] CPU 아키텍처 (x86, ARM) CPU 아키텍처를 설명하기 전에 ISA 개념을 알고 있으면 좋을 듯 ISA: Instruction Set Architecture는 CPU가 이해할 수 있는 명령어 집합이다.이게 각각의 CPU 아키텍처마다 다름.따라서 응용 프로그램이 해당 CPU에서 실행될 수 있도록 컴파일 할 때 맞는 CPU의 ISA, CPU 아키텍처에 따라야함. CPU 아키텍처는 CPU의 설계(내부 구성요소, 데이터 버스, 레지스터)와 명령어 집합 (ISA)를 정의한다.이는 다른 하드웨어와 소프트웨어 간의 상호작용에 사용되는 인터페이스 역할을 함 CPU 아키텍처 종류x86 아키텍처 (CISC: Complex Instruction Set Computing 계열)이름대로 복잡하고 다양한 명령어를 지원함. 그래서 한 개의 긴 명령어로 여러 .. 2025. 3. 10. [컴퓨터구조] 캐시 메모리 (개념, 역할, 매핑, 지역성) 캐시 메모리의 개념과 역할에 대해 설명해주세요.데이터를 임시로 저장해두는 메모리디바이스간 처리 속도 차이를 해소하기 위한 버퍼 역할 (주기억장치와 CPU사이에 위치)ex. 한번 사용한 데이터를 캐시에 저장해두고 이후에 동일한 데이터를 불러올 때 하드 디스크에서 불러오지 않아도 되도록 하여 처리 시간을 단축시킴.캐시 성능은 CPU가 호출하는 데이터가 캐시에 저장되어 있는 확률로 결정된다. 따라서 CPU가 호출할 만한 데이터를 어느정도 예측하는 것이 필요함매핑: 캐시 메모리와 주기억장치 사이에서 정보를 옮기는 것직접매핑: 데이터의 원래 주소를 캐시 라인 개수로 나눈 나머지가 가리키는 주소에 저장. 충돌이 자주 발생해서 교체가 잦음. 구현이 쉬움.연관매핑: 캐시 라인에서 빈 곳 아무데나 혹은 빈 곳이 없다면 .. 2025. 3. 10. [백준 1743] 음식물 피하기 (Swift) https://www.acmicpc.net/problem/1743 BFSN*M 격자 판에 K개의 음식물의 위치가 (r,c) 로 주어지고, 인접한 음식들의 묶음 중 가장 큰 묶음의 크기를 출력하는 문제(인접 : 상하좌우로 연결되어 있음) 접근방법우선 2차원 배열 map에 음식물의 위치를 표시하고, map의 모든칸을 확인하면서 방문여부와 음식물여부를 확인해서,방문한 적이 없고 음식물인 칸을 큐에 추가한다.그럼 이제 이 칸이 속한 음식물 묶음의 크기를 BFS를 통해서 구한다. (인접한 음식물을 큐에 넣기, 큐가 빌 때까지 반복, 큐에서 뺄 때 마다 음식물 묶음의 크기 +1)큐가 비어서 반복문이 종료되면 해당 음식물 묶음의 크기를 현재까지 최대 음식물 묶음의 크기를 저장하는 변수 result 와 비교해서큰 값을.. 2025. 3. 10. [백준 2290] LCD Test (Swift) https://www.acmicpc.net/problem/2290구현 2 1234567890 Given numbers (1234567890 as in the example) should be displayed on the LCD display.(my korean keyboard doesn't work..; suddenly.. I may correct this...in the near future.) the first input number (= s) indicates the length of each line that makes up the number display.So you need to make the output displaying the second numbers as in below stri.. 2025. 3. 6. [백준 9470] Strahler 순서 (Swift) https://www.acmicpc.net/problem/9470하천계의 Strahler 순서는 다음과 같이 구할 수 있다.강의 근원인 노드의 순서는 1이다.나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.재귀방향그래프가 위 그림 처럼 주어졌을 때 각 노드에 순서를 위의 규칙과 같이 구할 수 있다. 이때 마지막 노드인 바다와 만나는 노드의 순서가 이 하천계 그래프의 Strahler의 순서가 되는데 이를 구하는 문제 접근방법처음에 Strahler 순서가 무엇인지를 이해하는데 시간이 걸렸다. 결국 더이상 나가는 강이 없는 노드인 마지막 번째 노드의 순서를 구하는 문.. 2025. 3. 5. [백준 15989] 1, 2, 3 더하기 4 (Swift) https://www.acmicpc.net/problem/15989DP정수 n을 입력받아서 그 수가 1,2,3 들의 합으로 만들어질 수 있는 경우의 수를 출력하는 문제.순서는 상관없다. 접근방법한참 고민하다가 다른 블로그를 보고 풀었는데, 풀이만 간단하게 써있는 걸로는 이해가 잘 안갔다.대부분 점화식을 구해서 풀이하는 것 같았고, 가장 이해가 잘 됐던 설명은1. 모든 수가 1로만 더해서 만들어 질 수 있는 경우를 1가지는 갖고 있음 -> 그래서 1부터 10000까지의 수에 해당하는 경우의 수를 1로 초기화한다.- 1: 1- 2: 1+1- 3: 1+1+1- 4: 1+1+1+12. 그리고 이제 각 수가 1과 2만 더해서 만들어질 수 있는 경우의 수를 구해서 더해주는데, 이는 본인(N)에서 2를 뺀 수(N-2.. 2025. 3. 4. [백준 2178] 미로 탐색 (Swift) https://www.acmicpc.net/problem/2178 BFS1,1칸에서 N,M칸으로 이동하는데 거쳐야할 최소 칸 수 구하는 문제단 1로 표시된 칸으로만 갈 수 있음 접근방법BFS방식으로 큐를 사용해서 풀었다.dist 라고 해당 칸까지 거쳐온 칸 수를 저장하는 이차원 배열을 만들어서 썼는데, 큐에 칸을 넣을 때도 아직 방문하지 않은, 즉 dist 의 값이 0인 칸만 넣었다. 근데 아무래도 BFS니까 처음 그 칸에 도달하는 게 가장 최단 경로인게 맞긴 할텐데 비교할 필요가 아예 없나..? 비교하면 시간초과뜸BFS니깐 뭐..되겠지.. 소스코드 import Foundationfunc solution() { var map:[[Character]] = [] let NM:[Int] = (rea.. 2025. 3. 3. [백준 16506] CPU (Swift) https://www.acmicpc.net/problem/16506 구현아래와 같이 어셈블리어를 아래 표의 규칙에 따라 기계어로 변환하는 문제완전 구현 문제다MOVC 1 0 5 --> 0010100010000101접근방법어셈블리어를 띄어쓰기 기준으로 구분해서 모두 조건별로 기계어 코드를 구해서 합쳐서 출력하면 끝~ 오답노트 중간에 print()를 잘못넣어둬서 출력형식이 다르다고 계속 뜨더라구요.조심하십쇼 소스코드import Foundationfunc solution() -> [String] { let map:[String:String] = [ "ADD":"00000", "ADDC":"00001", "SUB":"00010", "SUBC":"00.. 2025. 2. 27. [백준 16197] 두 동전 (Swift) https://www.acmicpc.net/problem/16197 DFS BFS아래와 같은 보드에 #은 벽, . 은 빈칸, o는 동전이다. 동전은 2개만 존재함6 2.#.#.#o#o###네 방향키를 누를 수 있고, 누를 때 마다 두 동전이 그 방향으로 한칸씩 동시에 이동한다. 벽이 있는 칸으로는 이동할 수 없음 (단 이동 카운트는 체크) 이동하려는 칸에 다른 동전이 있어도 이동할 수 있음 이때, 두 동전 중 하나만 떨어지는 최소 횟수를 출력하는 문제, 단, 10번 보다 버튼을 더 많이 눌러야 하거나 두 동전을 떨어뜨릴 수 없는 경우 -1을 출력한다. 접근방법BFS를 곁들인..DFS식으로 구현하되 모든 경우를 고려하는게 관건이었던 문제였다.dfs 함수 인자로 두 동전의 현 위치와 현재까지 누른 버튼 횟수.. 2025. 2. 26. [백준 1890] 점프 (Swift) https://www.acmicpc.net/problem/1890 DP42 3 3 11 2 1 31 2 3 13 1 1 0 현재 칸에서 우측 or 아래측으로 이동할 수 있는 칸 수가 각 칸에 명시되어 있는 위의 표를 보고1,1칸에서 N,N칸에 도달할 수 있는 경우를 출력하는 문제 접근방법DP 배열에 해당 칸까지 오는 경우의 수를 저장한다. 0,0 칸에서 시작하므로 이 칸은 1로 시작해서 맨 위칸 부터 왼쪽에서 오른쪽으로 순회하면서 각 칸에 올 수 있는 경우의 수를 더해가면 된다. 처음에는 BFS로 했었는데 그러면 이미 방문한 노드를 다시 방문할 수 있어서 시간복잡도가 더 올라가는 듯 오답노트마지막 칸에 갔을 때는 중복되니까 반복문 돌지 않고 종료해야한다. 소스코드import Foundationfunc s.. 2025. 2. 26. 이전 1 2 3 4 5 6 7 ··· 27 다음 728x90
