Sad Puppy 3 개발자 아지트 :: 개발자 아지트

 

레퍼런스 타입은 참조형 변수이므로 프리미타입 보다 연산 속도가 느림 

따라서 프리미티브 타입을 주로 사용하는 것을 권장함

 

레퍼런스 타입이란 Integer, Long,Float, Double을 말하고

프리미티브 타입은 int, long, float, double을 말함

 

그러나 레퍼런스 타입에 대해서는 컬렉션 프레임워크 사용시, Integer, Float 타입을 저장할 때 사용하므로 알고는 있어야함. 
*컬렉션 프레임워크: 데이터를 저장하는 자료구조와 알고리즘을 구조화 하여 클래스로 구현해놓은 것을 말함

 

컬렉션 프레임워크

컬렉션 프레임워크는 다양한 자료구조를 직접 구현하지 않고 사용하게 해준다. 

주로 리스트(ArrayList), 스택(Stack), 큐(Queue), 데크(ArrayDeque), 해시맵(HashMap) 등을 사용한다. 

 

배열

import java.util.Arrays;

public class Test {

	public static void main(String[] args) {
		
		int[] array = { 2, 2, 2, 5 };
		
		// 배열을 출력할 때, java.util.Arrays의 toString()을 사용하면 쉽다.
        System.out.println(Arrays.toString(array)); // [2, 2, 2, 5]
		
		
	}

}

 

 

리스트

package Mar0308;

import java.util.ArrayList;

public class Test {	
	public static void main(String[] args) {
    
		// 리스트 객체 생성
		ArrayList<Integer> list = new ArrayList<>();
		
		list.add(1);
		list.add(2);
		
		System.out.println(list.get(1)); // 2
		System.out.println(list); // [1, 2]
		
	}
}

 

해시맵

해시맵은 키와 값 쌍을 저장하는 해시 테이블로 구현되어 있음

 

package Mar0308;

import java.util.HashMap;

public class Test {	
	public static void main(String[] args) {
		
		// 키는 문자열, 값은 정수형을 저장하는 해시맵 선언
		HashMap<String, Integer> map = new HashMap<>();
		
		// 해시맵 값 삽입
		map.put("vanilla cream cold brew", 1);
		map.put("ice americano", 2);
		map.put("ice vanilla latte", 3);
		
		// 해시맵 값 출력
		System.out.println(map); // {vanila cream cold brew=1, ice americano=2, ice vanila latte=3}
		
		
		
		// 해시맵에서 데이터 검색
		String key = "ice americano";
		
		if(map.containsKey(key)) {
			int value = map.get(key);
			System.out.println("key: " + key +  " value: " + value);
		}else {
			System.out.println("can't find");
		}
	
		
		// 해시맵 수정
		
		map.put("ice americano", 100);
		System.out.println(map); // {vanila cream cold brew=1, ice americano=100, ice vanila latte=3}
		
		// 해시맵 삭제
		
		map.remove("ice vanilla latte");
		System.out.println(map); // {vanila cream cold brew=1, ice americano=100}
		
		
	}

}

 

문자열

문자열은 문자들이 배열의 형태로 구성되어 있는 것이고, 이뮤터블 객체(변경할 수 없는 객체)이다. 

시간 복잡도 관점에서 사용시 주의 해야 한다. String의 값을 변경하는 연산이 많을 때는, StringBuilder 클래스나 StringBuffer클래스를 사용하는 것이 효율적이다.  

 

package Mar0308;

public class Test {	
	public static void main(String[] args) {
		
		// 문자열은 큰따옴표를 사용하여 표현한다. 
		String strr = "hi";
		
		// 문자열 추가 및 삭제 
		// 이때, 문자열은 이뮤터블 객체이므로 기존 객체를 수정하지 않고 새로운 객체를 생성하여 반환한다. 
		
		strr += "!!";
		
		// 반환시 기존 객체는 버리고 새로 생성한 객체만 사용함. 
		
		System.out.println(strr); // "hi!!"
		
		// 문자열 수정
		
		// replace(a, b) 
		// a에는 찾을 문자열, b에는 변경할 문자열 넣어 사용
		
		strr = strr.replace("i", "ello"); // "i" 를 모두 삭제함
		System.out.println(strr); // "hello!!"
		
	}
}

 

 

메서드

람다식

다른 말로 익명 함수라고도 한다. 코드에서 딱 한번 실행할 목적으로 사용하거나 함수 자체를 다른 함수의 인수로 전달할 때도 사용할 수 있다. 가독성이 좋아진다. 

 

package Mar0308;

import java.util.Arrays;
import java.util.Comparator;

public class Test {	
	
	private static class Node{
		int dest, cost;
		
		public Node(int dest, int cost) {
			this.dest = dest;
			this.cost = cost;
		}
	}
	
	public static void main(String[] args) {
		Node[] nodes = new Node[5];
		nodes[0] = new Node(1, 11);
		nodes[1] = new Node(2, 21);
		nodes[2] = new Node(3, 16);
		nodes[3] = new Node(4, 6);
		nodes[4] = new Node(5, 26);
        
        // 아래의 람다식과 일반식은 같은 역할을 수행한다...
		
		// 람다식
		Arrays.sort(nodes, (o1, o2) -> Integer.compare(o1.cost, o2.cost));
		
		// 일반식 
		Arrays.sort(nodes, new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				return Integer.compare(o1.cost, o2.cost);
			}
		});
		
		
		System.out.println(Arrays.toString(nodes));
				
	}

}

 

 

 

'Java > Java입문' 카테고리의 다른 글

반복문  (0) 2024.07.05
조건문  (0) 2024.07.05
연산자  (0) 2024.07.05
자바 자료구조 구현 - 큐, ArrayDeque  (0) 2024.03.08
자바 자료구조 구현 - 배열, ArrayList(리스트)  (0) 2024.03.08

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억번임을 기억하기

 

시간 복잡도 N의 가용 범위
O(N!) 10
O(2^N) 20~25
O(N^3) 200~300
O(N^2) 3,000~5,000
O(NlogN) 100만
O(N) 1,000~2,000만
O(logN) 10억

 

(백준한정-파이썬) 추가시간 없음 이라는 말이란?

=> 파이썬은 기존대로 1초에 2천만번 연산 가능함
(원래는 이런말 없으면 원만하게 정답 처리를 해주기 위해서 1초에 1억번까지 연상 가능하도록 해줌. )

 

 

https://www.acmicpc.net/problem/2667

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

문제설명

지도에서  현재 자신이 있는 곳(집)에서 집이 상하좌우 중 어느 한 곳이라도 연속이 되면 단지로 판단하고, 단지의 개수, 단지에 속한 집의 개수를 세아려서 오름차순으로 정렬하여 한줄에 하나씩 출력한다. 

문제 해결 방법

BFS로 문제를 풀었다. 


코드 구현

import java.io.InputStreamReader;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N;
	public static int cnt = 0;
	public static int totalCnt = 0;
	public static int[][] graph;
	public static int[] dx = {1, -1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	public static String A="";
	public static int[] sortt;

	public static ArrayList<Integer> list = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < N; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				BFS(i, j);
				cnt=0;
			}
		}
		
		System.out.println(totalCnt);
		
		Collections.sort(list);
			
		for(Object a : list) {
			System.out.println(a);
		}
		
	}
	
	public static void BFS(int start1, int start2) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(start1, start2));
		cnt = 0;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			if(graph[p.x][p.y]==1) {
				graph[p.x][p.y] = 9;
				cnt+=1;
			}
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				
				
				if(x < 0 || y < 0 || x >= N || y >= N) {
					continue;
				}
				
				if(graph[p.x][p.y]==0) {
					if(graph[x][y]==1) {
					}
				}
				
				
				if(graph[x][y]==1 && graph[p.x][p.y]!=0) {
					q.add(new Point(x, y));
					graph[x][y] = 9;
					cnt += 1;
				}
			}
			
		}
		
		if (cnt!=0) {
			totalCnt+=1;=
			list.add(cnt);
		}
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

처음에 ArrayList 사용할 생각을 못했다.
문자열에 각 단지의 개수를 추가한 후, 출력할 때 문자 하나하나 CharAt()으로 잘라서 출력했더니,
단지의 수가 9가 넘는 것들(두자리 수)의 값을 출력해야할 상황에는 다 런타임 에러가 났다. 

ArrayList가 답이다,, 이것을 이용하면 Collections를 이용해서  sort도 굉장히 편하게 할 수 있다.. 

버티지 말자~ 모르면 찾아보자 

'CodingTest > solved - Java' 카테고리의 다른 글

[프로그래머스 lv1]두 개 뽑아서 더하기  (0) 2024.03.08
[백준2606] 바이러스  (0) 2024.03.05
[백준2178] 미로 탐색  (0) 2024.03.05
[백준1260] DFS와 BFS  (0) 2024.03.04

https://www.acmicpc.net/problem/2606

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍

www.acmicpc.net

문제설명

컴퓨터는 네트워크를 통해 연결되어있다. (이것을 읽으면 딱 그래프가 연상된다)

1번 컴퓨터가 웜바이러스가 걸렸고, 이 컴퓨터와 네트워크를 통해 연결되었다면, 모두 바이러스에 걸리게된다. 

이때, 1번 컴퓨터를 통해 웜바이러스에 걸린 컴퓨터의 대수는?

 

문제 해결 방법

BFS를 이용하였고, 큐를 통해 구현하였다. 

코드 구현

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N, M;
	public static int cnt = 0;
	public static boolean[] visited;
	public static int[][] graph;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		Arrays.fill(visited, false);
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a - 1][b - 1] = 1;
			graph[b - 1][a - 1] = 1;
		}
		bfs(0);
		System.out.println(cnt);
		
	}
	
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			
			if(!visited[nodeIndex]) {
				visited[nodeIndex]= true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i] == 1 && !visited[i]) {
					visited[i] = true;
					cnt+=1;
					q.offer(i);
				}
			}
		}
	}
}

 

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

아직 살짝 문법적으로 헷깔리는점이 어려울뿐 ㅎㅎ

'CodingTest > solved - Java' 카테고리의 다른 글

[프로그래머스 lv1]두 개 뽑아서 더하기  (0) 2024.03.08
[백준2667] 단지번호붙이기  (0) 2024.03.06
[백준2178] 미로 탐색  (0) 2024.03.05
[백준1260] DFS와 BFS  (0) 2024.03.04

https://www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

 

문제설명

목적지를 향해 미로를 탐색하여 이동할 때 지나야 하는 최소 칸수를 구한다. 


문제 해결 방법

BFS로 풀었다. 


코드 구현

import java.io.BufferedReader;
import java.awt.Point;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static int N, M;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int[][] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//1,1에서 출발 
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[N][M];
		
		for(int i = 0; i<N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		//N, M 위치로 이동
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		
		bfs();
		System.out.println(graph[N-1][M-1]);
		// BFS 

	}
	
	public static void bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0,0));
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				if(x<0 || y<0 || x>=N || y>=M) {
					continue;
				}
				if(graph[x][y] == 1) {
					q.add(new Point(x, y));
					graph[x][y]=graph[p.x][p.y]+1;
				}

			}
		}	
	}
}

 

시간/공간 복잡도

O(N^2)


최적화 및 개선

하지않음 


어려웠던 점

좌표를 어떻게 저장해야할까 고민을 많이 하다가 

구글링해서 Point를 사용하여 문제를 해결했다. 

'CodingTest > solved - Java' 카테고리의 다른 글

[프로그래머스 lv1]두 개 뽑아서 더하기  (0) 2024.03.08
[백준2667] 단지번호붙이기  (0) 2024.03.06
[백준2606] 바이러스  (0) 2024.03.05
[백준1260] DFS와 BFS  (0) 2024.03.04

 

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

문제설명

단순 DFS, BFS 구현 문제이다!

 

문제 해결 방법

DFS는 스택으로, BFS는 큐로 문제를 풀었다. !

 

코드 구현

package Mar0304;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class P_1260 {
	public static int N, M, V;
	public static boolean[] visited;
	public static int[][] graph;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			visited[i]=false;
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a-1][b-1] = 1;
			graph[b-1][a-1] = 1;
		}
		
		DFS(V-1);
		
		Arrays.fill(visited, false);
		System.out.println("");
		BFS(V-1);
		
		
	}
	
	// DFS
	public static void DFS(int start) {
		//visited[start] = true;
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		
		
		while(!stack.isEmpty()) {
			int current = stack.pop();
			
			if(!visited[current]) {
				System.out.print((current + 1) + " ");
				visited[current] = true;
				
			}
			
			for(int i = N - 1; i >= 0; i--) {
				if(!visited[i]) {
					if(graph[current][i] == 1) {
						stack.push(i);
					}
				}
			}

		}
		
	}
	
	// BFS
	public static void BFS(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		//visited[start] = true;
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			if(!visited[nodeIndex]) {
				System.out.print((nodeIndex + 1) + " ");
				visited[nodeIndex] = true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i]==1 && !visited[i]) {
					q.offer(i);
				}
			}
			
		}
		
		
	}
}

 

시간/공간 복잡도

O(N^2)


최적화 및 개선

하지않음


어려웠던 점

문법이 손에 안익어서 어려웠다. 

'CodingTest > solved - Java' 카테고리의 다른 글

[프로그래머스 lv1]두 개 뽑아서 더하기  (0) 2024.03.08
[백준2667] 단지번호붙이기  (0) 2024.03.06
[백준2606] 바이러스  (0) 2024.03.05
[백준2178] 미로 탐색  (0) 2024.03.05

슬라이스

 

  • 동적 배열, 동적 배열이란 자동으로 배열 크기를 증가시키는 자료구조이다. ⇒ 관리 용이
  • 슬라이싱 기능을 이용해 배열의 일부를 나타내는 슬라이스를 만들 수 있음

 


사용법

 

아래와 같이 사용하면 고정된 크기의 배열을 사용하게됨.

var array [10]int

 

슬라이스 사용: 배열의 개수를 적지 않고 선언함.

-아래의 코드를 작성하면, 슬라이스를 초기화 하지 않은것이고, 길이가 0인 슬라이스가 만들어짐

이때, 슬라이스 길이를 초과해서 접근하면 런 타임 에러가 발생함

var slice []int

 

슬라이스 초기화 방법 1.

var slice1 = []int{1,2,3} 
var slice2 = []int{1, 5:2, 10:3} // [1 0 0 0 0 2 0 0 0 0 3]

 

슬라이스 초기화 방법 2. make() 내장 함수 사용.

var slice = make([]int, 3) // 타입, 배열의 길이, 각 요소 값은 int타입의 기본값인 0으로 채워짐

 

슬라이스 접근- C에서의 접근과 동일.

슬라이스 순회- 반복문을 통해서 순회함 len함수, range함수 사용

슬라이스 요소 추가- python에서 사용하는 append를 사용, 여러값 추가 가능


슬라이스 동작 원리

 

  • 슬라이스는 배열과 비슷하지만, 제대로된 동작 원리 이해가 필요함
  • 내장 타입이라 내부 구현이 감춰져 있음(reflect 패키지의 SliceHeader 구조체를 사용해 내부 구현을 살펴볼 수 있음)
  • 슬라이스 내부 정의는 다음과 같음

-배열을 가리키는 포인터

-배열 요소 개수를 나타내는 len

-전체 배열 길이를 나타내는 cap

필드로 구성된 구조체임

  • 슬라이스 변수 대입 시 배열에 비해서 사용되는 메모리나 속도에 이점이 있다. (?)

-make함수를 통해 슬라이스를 선언할 수 있음


슬라이스와 배열의 동작 차이

 

동작 차이의 원인

-go 언어에서 모든 값의 대입은 복사로 일어남. (함수의 인수로 전달될 때, 다른 변수에 대입할 때 등)

 

복사는 타입의 값이 복사됨.

 

포인터는 포인터의 값인 메모리 주소가 복사됨

구조체는 구조체의 모든 필드가 복사됨

배열은 배열의 모든 값이 복사됨.

 

슬라이스의 경우, 슬라이스 내부의 배열을 가리키는 포인터, len, cap만 복사되므로, 실제 배열의 값을 복사하는건 아님 .


슬라이싱

 

-배열의 일부를 집어내는 기능

-슬라이싱을 이용하면 슬라이스를 반환함(즉, 잘린 부분)

 

array[startIndex:endIndex]// 이때 슬라이스는 array의 startIndex~endIndex-1까지 슬라이싱 값

 

 

슬라이싱은 슬라이스도 슬라이싱 할 수 있다.

 

슬라이싱시, startIndex 자리를 비워두면 0으로 인식한다.

슬라이싱시, endIndex 자리를 비워두면 특정 요소부터 끝 요소 까지 슬라이싱 한다.

startIndex, endIndex를 둘다 비워두면 대상을 전체에 대해 슬라이싱한다.

 

슬라이싱시, 인덱스 3개를 사용하면 cap의 크기를 조절할 수 있다.

마지막 인덱스를 사용하면 대상 배열의 전체 길이를 사용하는게 아닌, 마지막 인덱스까지만 배열을 사용할 수 있음

 

*배열이나 슬라이스 뒤에 …를 붙이면, 모든 요솟값을 넣어준 것과 같게 됨.

 

copy함수를 이용하여 슬라이스를 복사할 수 있다.


슬라이스 요소 삭제

 

슬라이스의 중간 요소를 삭제하기 위해서는 C 배열에서 특정 인덱스의 값을 삭제할 때 처럼, 삭제한 인덱스 이후의 인덱스에 대해 일일이 값을 당겨줘야 한다.

이때, append()함수를 사용하면 코드를 한줄로 이를 해결할 수 있다.

지우고자 하는 값의 인덱스만 제외하고 append함수를 통해 각 값들을 복사한다.


슬라이스 요소 추가

 

만약, 슬라이스 요소를 슬라이스 중간에 추가 하고자 하는 경우

  • append함수를 통한 슬라이스 맨 뒤에 요소 추가(임의의 값)
  • 맨 뒤 값부터 삽입하려는 인덱스까지의 요소들을 한 칸씩 뒤로 밀어줌(하나씩 뒤로 복사)
  • 삽입하려는 값을 삽입하고자 하는 인덱스로 이동시킨다.

이와 같은 과정을 append()함수를 중첩 사용한 코드 한줄로 사용 가능하다.


슬라이스 정렬

 

-Go 언어에서 기본 제공하는 sort 패키지를 통해 슬라이스를 정렬할 수 있다.

-sort 패키지는 python에서 사용하는 sort함수와 비슷하다.

 

import(
			"sort"
)
//s라는 int타입의 정렬되지 않은 임의의 슬라이스가 있다. 
sort.Ints(s) // 정렬 

// 만약 float타입의 슬라이스를 정렬하고자 한다면 
// Float64s()함수를 사용하면 된다.  

 

-Go에서는 구조체 슬라이스도 정렬할 수 있다.


메서드

 

메서드란?

-함수의 일종

-Go언어에는 클래스가 없는 관계로, 구조체 밖에 메서드를 지정함. 구조체 밖에 메소드를 정의 할때 리시버라는 기능을 사용함

 

리시버란?

-구조체 밖에 메서드가 있다. 따라서 해당 메서드는 어느 구조체에 속하는지 표시해야 하고, 이때 리시버를 사용한다.

즉, 리시버는 메서드가 속하는 타입을 알려주는 기법임.

 

효과는?

-메서드를 사용하여 데이터와 기능이 묶이니 응집도가 높아짐

-코드 재사용성 용이

-모듈화로 코드 가독성이 좋아짐

 

메서드 선언

 

func(r Rabbit) info() int { // r Rabbit은 리시버이고 소괄호로 표시함. info()는 메서드의 이름이다. 
	return r.width * r.height
}

 

 

info() 메서드는 Rabbit 타입에 속한다.

구조체 변수 r은 해당 메서드에서 매개변수처럼 사용된다.

리시버는 모든 로컬 타입(해당 패키지 안에서 type 키워드로 선언된 타입)이 가능함

따라서 패키지 내에 선언된 구조체 및 별칭 타입들이 리시버가 될 수 있다.

 

package main

import "fmt"

type accoutn struct {
	balance int
}

func withdrawFunc(a *account, amount int) { // 함수 표현
	a.balance -= amount
}

func (a *account) withdrawMethod(amout int){ // 메서드 표현 
	a.balance -= amount
}

func main(){
	a:= &account{ 100 } // balnace가 100인 account 포인터 변수 생성
}

withdrawFunc(a, 30) // 함수 형태 호출

a.withdrawMethod(30) // 메서드 형태 호출 

// 위의 함수와 메서드는 똑같은 역할을 하지만 형태가 다르므로, 호출 방법도 다르다.
// 메서드는 해당 리시버 타입에 속한다. 따라서 리시버를 점 연산자를 사용해 호출함

// 구조체 필드에 접근할 때 처럼 . 연산자를 사용해 해당 타입에 속한 메서드를 호출할 수 있다.

 

 

 

별칭 리시버 타입

 

별칭 리시버 타입은 별칭일 뿐 리시버가 될 수 있고, 메서드를 가질 수 있다.

Int와 같은 내장 타입들도 별칭 타입을 활용해서 메서드를 가질 수 있다.

기본 내장 타입들은 별칭 타입으로 변환하여 메서드를 선언할 수 있다.

package main

import "fmt"

// int 타입의 별칭인 사용자 정의 별칭 타입 userInt
type userInt int

// userInt 별칭 타입을 리시버로 갖는 메서드
func (a userInt) add(b int) int {
	return int(a) + b
}

func main() {
	var a userInt = 10
	fmt.Println(a.add(30))
	var b int = 20
	fmt.Println(userInt(b).add(50)) 
    // int 타입과 userInt 타입은 엄연히 다른 타입이므로 연산이 불가함 따라서
    // int 타입을 userInt 타입으로 형변환 하여 사용
}

 

 

메서드가 필요한 이유

 

함수도 있는데 왜 굳이 복잡하게 메서드라는걸 만든걸까?

 

함수와 메서드는 중요한 차이가 있다.

⇒ 소속 유무의 차이, 일반 함수는 어디에도 속하지 않지만, 메서드는 리시버에 속한다.

 

데이터와 관련된 기능을 메서드를 통해 구현하고 이를 데이터와 묶기 좋다.

따라서 코드 응집도를 높이는 중요한 역할을 한다. 좋은 코드는 결합도는 낮고 응집도는 높다. 

메소드는 해당 부분에 중요한 역할을 한다. 

 

코드 응집도가 떨어지면, 새 기능을 추가할 때 흩어진 모든 관련 부분을 검토하고 고쳐야 하는 문제가 발생한다.

코드 수정 범위가 늘어나면 관리는 복잡해지고, 실수가 발생할 확률이 높아지고, 따라서 버그를 만들 확률도 높아진다.

따라서 코드 응집도를 높일 필요가 있다.

 

객체지향 중심으로 변화

메서드가 등장함으로써, 메서드로 데이터와 기능을 묶을 수 있게 되고, 이것은 객체로 동작할 수 있게 됐다.

이는 절차 중심에서 객체 간 관계 중심으로 프로그래밍 패러다임이 변화를 일으켰다. 

과거에는 기능 호출 순서도를 나타내는 플로우차트를 중시했지만, 이제는 객체간 관계를 나타내는 클래스 다이어그램이 더 중요하게 됐다. 

 

객체란 데이터와 기능을 갖는 타입이고, 해당 객체의 타입의 인스턴스를 객체 인스턴스라고 한다. 

이런 객체 인스턴스들이 서로 상호작용을 함으로써, 객체 간의 관계 중심으로 프로그래밍 패러다임이 변화했다. 

(OOP, Object Oriented Programming)

 

포인터 메서드와 값 타입 메서드

리시버를 일반 값 타입과 포인터 값으로 정의할 수 있다. 

 

package main

import "fmt"

type account struct {
	balance int
	firstName string
	lastName string
}

// 포인터 메서드
func (a1 *account) withdrawPointer(amount int) {
	a1.balance -= amount
}

// 값 메서드
func (a2 *account) withdrawValue(amount int){
	a2.balance -=amount
}

// 변경된 값 반환 메서드
func (a3 account) withdrawReturnValue(amount int) account{
	a3.balance -= amount
	return a3
}

func main() {
	var mainA *account = &account{ 100, "Joe", "Park"}
	mainA.withdrawPointer(30) // 포인터 메서드 호출, mainA의 주솟 값이 a1으로 복사됨 
    // mainA와 a1은 같은 인스턴스를 바라봄
	fmt.Println(mainA.balance) // 70 출력

	mainA.withdrawValue(20) // 값 메서드 호출, mainA의 모든 값이 a2로 전달됨 
    // mainA와 a2는 서로 다른 인스턴스를 바라봄
	fmt.Println(mainA.balance) // 70 출력

	var mainB account = mainA.withdrawReturnValue(20) // mainB는 50
	fmt.Println(mainB.balance) // 값 메서드 값에서 변경된 값 반환 메서드 실행

	mainB.withdrawPointer(30) 
	fmt.Println(mainB.balance) // 20
}

 

메서드는 리시버의 타입을 그대로 따라가서 메서드는 리시버의 타입에 속함. 

포인터 메서드를 호출시, 포인터가 가리키는 메모리 주소값이 복사되고, 값 메소드 호출시, 리시버 타입의 모든 값이 복사됨. 

 

포인터 메서드는 메서드 내부의 리시버 값을 변경시킬 수 있음.

값 타입 메서드는 호출하는 쪽과, 메서드 내부의 값은 서로 다른 인스턴스이고, 따라서 메서드 내부 리시버 값을 변경시킬 수 없음

 

 

 

 

 

해당 글은 [Tucker의 Go 언어 프로그래밍] 18장~19장을 읽고 공부한 글입니다. 

https://school.programmers.co.kr/learn/courses/30/lessons/64061

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.

"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1, 5, 3] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

 

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.

board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.

  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.

moves 배열의 크기는 1 이상 1,000 이하입니다.

moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

 

입출력 예

board                                                                                  moves                result

[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]    [1,5,3,5,1,2,1,4]    4

 

입출력 예에 대한 설명

 

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

문제 해결 방법

스택 자료구조를 이용하여 문제를 해결하였음

코드 구현

def solution(board, moves):
    #시간 복잡도는 O(N^3)까지 가능함.
    answer = 0
    # 바구니의 크기는 무한대 
    basket = []
    cnt=0
    for move in moves:
        for i in board:
            if i[move-1] != 0: #만약 i 줄 배열에 move칸에 값이 0이 아니라면
                try: # 바스켓이 비었을 때, pop하는 것을 방지하기 위함
                    a=basket.pop() # 바구니에서 뽑아서 현재 넣을 것과 비교
                    if a == i[move-1]: # 공통된다면 지우고 카운트 증가 시키기
                        cnt+=2
                        i[move-1] = 0
                    else:
                        basket.append(a)
                        basket.append(i[move-1]) # 바구니에 추가해줌
                        i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
                except: #만약 바스켓이 비어있다면? 예외구문으로 
                    basket.append(i[move-1]) # 바구니에 추가해줌
                    i[move-1] = 0 # 바구니에 추가한 것은 0으로 처리함
                
                break # 해당 반복문 탈출 후, 다음 move조회
            else:# 만약 0이면
                continue #  다음 줄로 넘겨서 조회함 

    return cnt

시간/공간 복잡도

구현은 O(N^2)으로 하였음.

문제의 제한시간을 보면 O(N^3)으로 구현해도 문제 없을듯함.

최적화 및 개선

하지않음

어려웠던 점

없음

https://school.programmers.co.kr/learn/courses/3-/lessons/42584

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

prices의 길이는 2 이상 100,000 이하입니다.

 

입출력 예

prices    return

[1, 2, 3, 2, 3]      [4, 3, 1, 1, 0]

 

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.

2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.

3초 시점의 ₩3 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.

4초 시점의 ₩2 1초간 가격이 떨어지지 않았습니다.

5초 시점의 ₩3 0초간 가격이 떨어지지 않았습니다.

문제 해결 방법

아 이문제는 참 어렵다! 시간 복잡도는 O(N^2)에 맞추면 안되고 O(NlogN)까지 가능하다. 

그런데 이 문제 아무리생각해봐도 O(NlogN)로 풀기 어려웠다. 그래서 O(N^2)로 풀어봤는데,,, 끝이 안난다. 

이조건 맞추면 저 조건 안맞고, 저 조건 맞추면 이 조건 안맞고 그랬다. 

 

그래서 결국 답을 보고 이해했다. 

 

이 문제는 효율성을 해결하기 위해서는 반드시 스택으로 풀어야한다. 그런데 이 문제 스택을 어디에 적용할지 떠올리기가 참 어렵다. 

 

코드 주석으로 설명하였다. 

 

코드 구현

 

기존 코드 - 미해결

def solution(prices):
    #O(N)으로 구현
    answer = []
    
    prices=list(prices)
    stackk=[]
    newPrices=[]
    newPrices = list(prices)

    for i in range(len(prices)):
        
        if i == 0:
            stackk.append(prices[i])
        else:
            
            newPrices.reverse()
            if len(newPrices)==0:
                break
            
            newPrices.pop()
            newPrices.reverse()
            cnt=0

            #print('prices[i]', prices[i-1], 'newPrices', newPrices)
            for price in newPrices:
                #print('price', price)
                if prices[i-1]<=price:
                     cnt+=1
            
            answer.append(cnt)
            
    answer.append(0)  
    #print(answer)
    
    
    
    return answer

 

개선 코드 - 해결

 

def solution(prices):
    answer = []
    total = len(prices)
    answer = [0] * total
    #각 초 시점의 길이를 넣을 배열
    stackk = [0] 

    # 스택을 0으로 초기화 한 이유는 순회를 인덱스 1부터 하기 위해서임 
    # prices의 0번 인덱스는 스택에 넣고 시작한다. 
    
    for i in range(1, total):
        # 1부터 total까지 순회한다. 
        # 0번 인덱스부터 total 인덱스까지 순회할 때, 가격의 증가만 있다면,
        # 계속 stackk에 넣는다. 
        # 만약 가격이 떨어진다면 그때부터는 스택에서 꺼내어서 하락한 가격의 인덱스로부터 길이를 구한다. 
        while stackk and prices[stackk[-1]]>prices[i]:
            a=stackk.pop()
            answer[a]=i-a
        stackk.append(i)
        
    while stackk: # 스택이 빌 때까지 순회하여 길이를 찾아준다. 
    #이 스택은 최종적으로 증가한 값들만 남아있다. 
        a=stackk.pop()
        answer[a]=total-a-1
        
    #print(answer)
    
    return answer

 

시간/공간 복잡도

O(NlogN)

최적화 및 개선

많은 개선을 했다. 음 로직을 아예 뜯어고침 

어려웠던 점/느낀점

답지를 안보고 혼자 코드 로직을 생각할 수 있을때 까지 연습하는것 까지 했다. 

다음에 또 풀때는 잘 풀었으면 좋겠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1, 아닐 경우 0을 리턴해주면 됩니다.

 

예를 들어, 문자열 S = baabaa 라면

 

b aa baa → bb aa → aa →

 

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

 

문자열의 길이 : 1,000,000이하의 자연수

문자열은 모두 소문자로 이루어져 있습니다.

 

입출력 예

 

s         result

baabaa  1

cdcd     0

 

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

 

입출력 예 #2

문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.


문제 해결 방법

주어진 str을 list로 바꿔서 list 요소를 순회시킨다. 

스택으로 쓸 배열을 하나 만든다. 

첫번째 요소는 스택에 넣고,

두번째 요소부터는 스택에 있는 값을 꺼내어 비교한 후 같으면 아무 동작하지 않고 넘어간다. 

만약 같지 않으면, 꺼낸 값을 스택에 다시 넣고, 현재 보고있는 list 요소도 스택에 같이 넣는다. 

 

순회가 끝나고, 스택의 길이를 재봤을때, 길이가 0이면 1을 반환, 길이가 0보다 크면 0을 반환한다. 


코드 구현

def solution(s):
    #O(nLogN)으로 구현
    stakk =[]
    newS=s
    newS=list(newS)
    
    for i in range(len(newS)):
        if i == 0 or len(stakk)==0:
            stakk.append(newS[i])
        else:
            a = stakk.pop()
            if newS[i] == a:
                continue
            else:
                stakk.append(a)
                stakk.append(newS[i])
    
    if len(stakk)==0:
        return 1
    else:
         return 0


시간/공간 복잡도

문제 제한 사항을 보니 O(NlogN)으로 풀어야 할 것 같았다. 

나는 O(N)으로 구현하게 되었다. 


최적화 및 개선

안함


어려웠던 점

머릿속으로 확신을 가지고 구현한게 아니라 이게 맞나 싶었는데 풀렸다. 

이런식으로 풀면 안좋다 그러던데,,, 담엔 확신 가질만큼 종이에 로직을 써보고 문제 풀어야겠다.

+ Recent posts